c2c网站开发毕业设计,东莞网站营销公司,购物网站首页模板下载,网站定制案例微安电力$ POJ~1966~Cable~TV~Network $ $ solution: $ 第一眼可能让人很难下手#xff0c;但本就是冲着网络流来的#xff0c;所以我们直接一点。这道题我们要让这个联通图断开#xff0c;那么势必会有两个点变得不连通#xff0c;这道题的数据范围很小#xff0c;所以我们试着暴… $ POJ~1966~Cable~TV~Network $ $ solution: $ 第一眼可能让人很难下手但本就是冲着网络流来的所以我们直接一点。这道题我们要让这个联通图断开那么势必会有两个点变得不连通这道题的数据范围很小所以我们试着暴力枚举两个点。这样就变成了最小割。不过嗯割的东西怎么是点 为了靠近我们已经学得知识我们想办法看能不能割点变成割边。反正网络流最喜欢千变万化、左右建模了。。。于是我们引进书上的一个东西 一个节点可以拆成两个节点将原节点用中间那条边表示一条边可以拆成两条边将原边用中间那个点表示中间的边权为1代表这个点是否被割旁边的边权为inf是为了排除其影响因为它不可能被割掉我们用第一条和第三条性质可以解决这个问题。首先对于每个节点建立两个 $ i $ 和 $ in $ 节点。然后这两个节点之间用一条权值为1的有向边从 $ i $ 到 $ in $ 如果这条边在最小割中被割掉等价于原本的点被割掉。然后 $ i $ 节点连入边权值正无穷 $ in $ 节点连出边权值正无穷连正无穷是为了让割掉的边只能是中间的边。然后我们跑一遍最大流它对应的最小割里每条代表原来一个点因为权值为1所以流量就是答案。 注意我们的源汇点也要被分为两个点而网络流中的实际源点是 $ Sn $ 它连出边。因为源汇点的性质这两个点不可能被割掉所以它们中间不连边。 $ code: $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;int n,m,S,T;
int ans,top1;
int dep[505];
int tou[505];
int qi[505];
int f[55][55];struct su{int to,v,next;
}b[5005];inline int qr(){register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}inline void add(int x,int y,int v){ //注意博主加边自带反向b[top]su{y,v,tou[x]}; tou[x]top;b[top]su{x,0,tou[y]}; tou[y]top;
}inline bool bfs(int x){for(rg i1;ix;i)qi[i]tou[i],dep[i]0;queueint q; q.push(S); dep[S]1;while(!q.empty()){rg iq.front(); q.pop();for(rg jtou[i];j;jb[j].next)if(b[j].v!dep[b[j].to]){dep[b[j].to]dep[i]1;if(b[j].toT)return 1;q.push(b[j].to);}} return 0;
}inline int dfs(int i,int w){if(iT||!w)return w;rg restw,f;for(rg jqi[i];j;jb[j].next){if(b[j].vdep[b[j].to]dep[i]1){fdfs(b[j].to,min(w,b[j].v));if(!f){dep[b[j].to]-2; continue;}b[j].v-f; b[j^1].vf; w-f;} if(!w)break;}return rest-w;
}inline void solve(){rg res0; top1;for(rg i1;in*22;i) tou[i]0; //初始化for(rg i1;in;i){if(i!Si!T)add(i,in,1); //一点拆成两点中间连边for(rg j1;jn;j)if(f[i][j])add(in,j,1e9); //连边注意是否有加n操作} SSn;while(bfs(n*22)) resdfs(S,1e9); //DInicansmin(res,ans);
}int main(){//freopen(.in,r,stdin);//freopen(.out,w,stdout);rg tqr();while(t--){nqr();mqr();for(rg i1;in;i){for(rg ji;jn;j){f[i][j]f[j][i]0; //初始化}}for(rg i1;im;i){rg xqr()1,yqr()1;f[x][y]f[y][x]1; //邻接矩阵读边}if(n0||n2){puts(0);continue;}if(m0nn!2){puts(1);continue;}//特判这题有点卡细节ans1e9;for(rg i1;in;i){for(rg j1;jn;j){if(f[i][j]||ij)continue; //注意两个相邻的点不可能通过割点不联通Si;Tj; solve(); //枚举源汇点}} if(ans1e9)ansn; //无论怎么割点图都联通就输出nprintf(%d\n,ans);}return 0;
}转载于:https://www.cnblogs.com/812-xiao-wen/p/11257791.html
