Ahead
11.1.2018
例题
poj 2125
题意为选取一些点使得覆盖所有的边
仍然是最小割与割点，对于每一条边的两个点，从源点向每个点连一条删除从这个点出发的所有边的权值 即W- ，同理对每一个点向汇点连W+ 中间部分为图的边关系。 然后最大流即可 针对方案需要进行一次深搜，对于与源点连接的点，如果不能被访问到，那么一定是割去的，对于与汇点相连的如果被访问到那么一定是割去的代码
#include#include #include #include #include using namespace std;const int s = 1000,t = 1001;const int N = 40000,inf = 0x3f3f3f3f;int n,m;int to[N<<1],nxt[N<<1],last[N],w[N<<1],len=1;inline void ins(int x,int y,int c){ to[++len]=y,nxt[len]=last[x],w[len]=c,last[x]=len;}int h[N];bool vis[N];bool bfs(){ memset(h,0,sizeof(h)); queue q; vis[s]=1; q.push(s); h[s]=1; while(!q.empty()) { int x = q.front(); q.pop(); vis[x]=0; for(int k=last[x]; k; k=nxt[k]) { int y=to[k]; if(w[k] && !h[y]) { h[y] = h[x] + 1 ; if(!vis[y]) { vis[y]=1; q.push(y); } } } } return h[t]!=0;}int dfs(int x,int flow){ if(x==t) return flow; int res=flow; for(int k=last[x]; k; k=nxt[k]) { int y=to[k]; if(w[k] && h[y] == h[x]+1) { int t = dfs(y,min(w[k],res)); w[k]-=t; w[k^1]+=t; res-=t; if(res==0) break; } } if(res==flow) h[x]=0; return flow-res;}inline int dinic(){ int maxflow=0; while(bfs()) { int tmp = dfs(s,inf); while(tmp) { maxflow += tmp; tmp = dfs(s,inf); } } return maxflow;}bool ok[N];void DFS(int x){ ok[x]=1; for(int k=last[x]; k; k=nxt[k]) { int y=to[k]; if(!ok[y] && w[k]) DFS(y); }}int main(){ int x,y,z; scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) { scanf("%d",&z); ins(i+n,t,z),ins(t,i+n,0); } for(int i=1; i<=n; ++i) { scanf("%d",&z); ins(s,i,z),ins(i,s,0); } for(int i=1; i<=m; ++i) { scanf("%d%d",&x,&y); ins(x,y+n,inf),ins(y+n,x,0); } printf("%d\n",dinic()); int res=0; DFS(s); for(int i = 1; i <= n; i++) { if(!ok[i]) res++; if(ok[i + n]) res++; } printf("%d\n", res); for(int i = 1; i <= n; i++) { if(!ok[i]) printf("%d -\n", i); if(ok[i+n]) printf("%d +\n", i); } return 0;}