| Time Limit: 2000MS | Memory Limit: 65536K | |||
| Total Submissions: 8311 | Accepted: 2677 | Special Judge | ||
Description
Input
Output
Sample Input
3 6 1 2 3 4 2 1 1 2 1 1 3 2 1 2 3 1 2 3
Sample Output
5 3 1 + 2 - 2 +
Source
题意from mhy12345:给一张有向图，现在要选择一些点，删掉图中的所有边。具体操作为：选择点 i，可
以选择删除从 i 出发的所有有向边或者进入 i 的所有有向边，分别有个代价 ini 和
outi，求最小的代价删掉所有边。并输出删除方案。
建图 S-- w+ -->in-->out-- w- -->T
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=205,M=6005,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f; } int n,m,u,v,s,t,w[N]; struct edge{ int v,c,f,ne; }e[M<<1]; int cnt,h[N]; inline void ins(int u,int v,int c){ cnt++; e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt; } int cur[N],d[N],vis[N]; int q[N],head,tail; bool bfs(){ head=tail=1; memset(vis,0,sizeof(vis)); d[s]=1;vis[s]=1;q[tail++]=s; while(head!=tail){ int u=q[head++]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]&&e[i].c>e[i].f){ vis[v]=1;d[v]=d[u]+1; q[tail++]=v; if(v==t) return true; } } } return false; } int dfs(int u,int a){ if(u==t||a==0) return a; int flow=0,f; for(int &i=cur[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]==d[u]+1&&(f=dfs(v,min(e[i].c-e[i].f,a)))>0){ flow+=f; e[i].f+=f; e[((i-1)^1)+1].f-=f; a-=f; if(a==0) break; } } if(a) d[u]=-1; return flow; } int dinic(){ int flow=0; while(bfs()){ for(int i=s;i<=t;i++) cur[i]=h[i]; flow+=dfs(s,INF); } return flow; } void bfsSol(){ head=tail=1; memset(vis,0,sizeof(vis)); q[tail++]=s;vis[s]=1; while(head!=tail){ int u=q[head++]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]&&e[i].c>e[i].f){ vis[v]=1; q[tail++]=v; } } } } int cut[M]; void solve(){ int flow=dinic(); printf("%d\n",flow); bfsSol(); int num=0; for(int i=1;i<=n;i++){ if(!vis[i]) num++; if(vis[i+n]) num++; } printf("%d\n",num); for(int i=1;i<=n;i++){ if(!vis[i]) printf("%d +\n",i); if(vis[i+n]) printf("%d -\n",i); } } int main(){ //freopen("in.txt","r",stdin); n=read();m=read();s=0;t=n+n+1; for(int i=1;i<=n;i++) w[i]=read(),ins(s,i,w[i]); for(int i=1;i<=n;i++) w[i+n]=read(),ins(i+n,t,w[i+n]); for(int i=1;i<=m;i++){ u=read();v=read(); ins(v,u+n,INF); } solve(); }
POJ 2125 Destroying The Graph [最小割 打印方案]
原文：http://www.cnblogs.com/candy99/p/6347798.html