站内关键词排名软件,企业年金怎么查,济宁网站建设云科网络,白山市住房和城乡建设局网站网络流好题
给出A、B两个点集#xff0c;A、B之间有边相连#xff0c;而A和B的内部均无边相连。
题目要求求出最多删除A、B之间的多少边#xff0c;才能使得A中点的度数至少都为2#xff0c;B中点的度数也至少都为2。
先求出每个点的度数#xff0c;从每个点v出发…
网络流好题
给出A、B两个点集A、B之间有边相连而A和B的内部均无边相连。
题目要求求出最多删除A、B之间的多少边才能使得A中点的度数至少都为2B中点的度数也至少都为2。
先求出每个点的度数从每个点v出发最多能删除deg[v]-2条边注意这里是理想情况下不一定能删除这么多
那么我们就可以建立一个超级源点s和超级汇点t从s往A点集连边边的容量为deg[v]-2从B点集往t点连边变的容量为deg[u]-2
A和B之间的边流量全为1.这样的话从s点流到t的每一个为1的流量都相当于在原图里面删除了这条边。
跑一边最大流就可以得到最多能删除多少边了。在残余网络中做一些小操作就可以把剩余的边输出出来。
代码 #include bits/stdc.h
using namespace std;
const int MAXN 333;
int m,n,p;
int deg1[MAXN];
int deg2[MAXN];
using namespace std;
const int oo1e9;const int mm 200000;const int mn999;int node,src,dest,edge;int ver[mm],flow[mm],next[mm];int head[mn],work[mn],dis[mn],q[mn];void prepare(int _node,int _src,int _dest)
{node_node,src_src,dest_dest;for(int i0; inode; i)head[i]-1;edge0;
}void addedge(int u,int v,int c)
{ver[edge]v,flow[edge]c,next[edge]head[u],head[u]edge;ver[edge]u,flow[edge]0,next[edge]head[v],head[v]edge;
}bool Dinic_bfs()
{int i,u,v,l,r0;for(i0; inode; i)dis[i]-1;dis[q[r]src]0;for(l0; lr; l)for(ihead[uq[l]]; i0; inext[i])if(flow[i]dis[vver[i]]0){dis[q[r]v]dis[u]1;if(vdest)return 1;}return 0;
}
int Dinic_dfs(int u,int exp)
{if(udest)return exp;for(int iwork[u],v,tmp; i0; inext[i])if(flow[i]dis[vver[i]]dis[u]1(tmpDinic_dfs(v,min(exp,flow[i])))0){flow[i]-tmp;flow[i^1]tmp;return tmp;}return 0;
}
int Dinic_flow()
{int i,ret0,delta;while(Dinic_bfs()){for(i0; inode; i)work[i]head[i];while(deltaDinic_dfs(src,oo))retdelta;}return ret;
}
int main(){freopen(trade.in,r,stdin);freopen(trade.out,w,stdout);scanf(%d%d%d,m,n,p);prepare(mn2,0,mn1);for(int i 0;i p;i){int a,b;scanf(%d%d,a,b);deg1[a];deg2[b];addedge(a,bm,1);}int f 1;for(int i 1;i m;i){if(deg1[i] 2) {f 0;break;}}for(int i 1;i n;i){if(deg2[i] 2) {f 0;break;}}if(!f){puts(-1);return 0;}for(int i 1;i m;i){if(deg1[i] 2)addedge(0,i,deg1[i] - 2);}for(int i 1;i n;i){if(deg2[i] 2)addedge(im,nm1,deg2[i] - 2);}int res Dinic_flow();printf(%d\n,p - res);for(int i 0;i p;i){int tr i * 2;if(flow[tr] 1){printf(%d ,i1);}}return 0;
}
