linux建设网站,登陆Wordpress手机app,培训网站设计,企业备案信息哪里可以查题意#xff1a;
给出一副有 n n n个点#xff0c; m m m条边的无向图#xff0c;求出这副图的最小割点数
题意#xff1a; 首先对于有向图#xff0c;求他的最小割边#xff0c;只需要令每条边的容量为 1 1 1#xff0c;求出起点到终点的最大流就是最小割边数了。 容…题意
给出一副有 n n n个点 m m m条边的无向图求出这副图的最小割点数
题意 首先对于有向图求他的最小割边只需要令每条边的容量为 1 1 1求出起点到终点的最大流就是最小割边数了。 容量设为1的原因更多是反映这条路有没有流到达汇点不需要在乎数量 对无向图要求其最大流只需要对双向边都建反向边即可即 while(m--) {int u,v,w; cinuvw;add(u,v,w);add(v,u,0);add(v,u,w);add(u,v,0);
}此时要对无向图求最小割点数考虑将点化成边这样才符合最大流
考虑将一个点 u u u拆分成入点 u 1 u_{1} u1和出点 u 2 u_{2} u2此时同最小割边一样将这个边权设为 1 1 1但在拆分源点汇点时这两个点不可删去所以内部权值要设为inf
#includebits/stdc.h
using namespace std;using lllong long;
const int N2e25,M2e35,inf0x3fffffff;
const long long INF0x3fffffffffffffff,mod998244353;int ceil(int x,int y) {return x%y?x/y1:x/y;
}struct way {int to,next,cap;way()default;way(int to,int next,int cap) {this-toto;this-nextnext;this-capcap;}
}edge[M2];
int cnt1,head[N];void add(int u,int v,int cap) {edge[cnt]way(v,head[u],cap);head[u]cnt;
}int n,m,s,t,dis[N],now[N];bool bfs() {for(int i1;in;i) dis[i]inf;queueintq;q.push(s);dis[s]0;now[s]head[s];while(!q.empty()) {int uq.front();q.pop();for(int ihead[u];i;iedge[i].next) {auto [v,_,cap]edge[i];if(dis[v]infcap) {dis[v]dis[u]1;q.push(v); now[v]head[v];if(vt) return true;}}}return false;
}int dfs(int u,int flow) {if(ut) return flow;int ret0;for(int inow[u];(now[u]i);iedge[i].next) {auto [v,_,cap]edge[i];if(cap0||dis[v]!dis[u]1) continue;int nflowdfs(v,min(flow,cap));if(nflow0) dis[v]inf;else {edge[i].cap-nflow;edge[i^1].capnflow;retnflow;flow-nflow;}}return ret;
}int main() {#ifdef stdjudgefreopen(in.txt,r,stdin);auto TimeFlagFirstclock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cinnmst;for(int i1;in;i) {int cap(is||it)?inf:1;add(i,in,cap);add(in,i,0);}while(m--) {int u,v;cinuv;add(un,v,1);add(v,un,0);add(vn,u,1);add(u,vn,0);}tn;n1;int ans0;while(bfs()) ansdfs(s,inf);coutansendl;#ifdef stdjudgefreopen(CON,r,stdin);std::coutstd::endl耗时:std::clock()-TimeFlagFirstmsstd::endl;std::coutstd::flush;system(pause);#endifreturn 0;
}
