本文共 2007 字，大约阅读时间需要 6 分钟。
简单描述一下题目：
一个有向图，每个点删除入边有个权值，删除出边有另一个权值。则删除所有边最小权值？
所以，一条边有两种删除方式，要么选择起始点删出边，要么选择终止点删入边。显然是求分配方案。
关于分配方案，自然想到网络流，图中拆点，分为入边点，和出边点，这样权值也分离了，原来的边按逻辑连接对应入边点，和出边点。
这里我犹豫了好久，点权怎么处理。
网络流点权是一定要转化成边权的，一般点权有两种处理方案：
1，拆点，连边权值表示点权。一般用于最小费用最大流，但这道题，S或T连接边权值为INF，因为边权是INF，这样网络优化一下，把拆出的点与ST融合，就是方案2的网络流图了。
2，新设源汇点连接该点，连边表示权值。这样就是最小割问题，求原图每条边是分配出边点集还是入边点集。
关 于 最 小 割 的 割 边 或 割 点 ： \red{关于最小割的割边或割点：} 关于最小割的割边或割点：
最大流的流量就是最小割的开销，但S或T连接的满载边未必是最小割边，因为网络流有转嫁流量的性质，存在一种情况把大边的流量转嫁到小边，使所有小边满载，但边数量明显增加。
利用最小割的特性，用DFS搜索找S联通集，和T联通集的点，然后，点对应连接S或T的边就是割边。
// ShellDawn// POJ2125// No.32#include #include #include #include #include #include #define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;//#define maxn 105int E[maxn*2][maxn*2];int V[maxn*2];int N,M;int S,T;bool BFS(int s){ MM(V,0); queue q; q.push(s); V[s] = 1; while(!q.empty()){ int now = q.front(); q.pop(); for(int i=S;i<=T;i++){ if(V[i] == 0 && E[now][i] > 0){ V[i] = V[now] + 1; q.push(i); } } } if(V[T] > 0) return true; return false;}int DFS(int now,int minflow){ if(now == T) return minflow; int flow = 0; for(int i=S;i<=T && minflow;i++){ if(E[now][i] > 0 && V[i] == V[now] + 1){ int f = DFS(i,min(minflow,E[now][i])); minflow -= f; flow += f; E[now][i] -= f; E[i][now] += f; } } if(flow == 0) V[now] = 1; return flow;}void FindP(int now){ for(int i=1;i 0 && V[i] == 0 ){ V[i] = 1; FindP(i); } }}int main(){ while(~scanf("%d%d",&N,&M)){ S = 0; T = N+N+1; MM(E,0); int v; // 入点 1～N for(int i=1;i<=N;i++){ scanf("%d",&v); E[i][T] = v; } // 出点 N+1～N+N for(int i=N+1;i<=N+N;i++){ scanf("%d",&v); E[S][i] = v; } while(M--){ int a,b; scanf("%d%d",&a,&b); E[a+N][b] = INF; } int ans = 0; while(BFS(S)) ans+=DFS(S,INF); printf("%d\n",ans); MM(V,0); FindP(S); int cnt = 0; for(int i=1;i<=N;i++){ if(V[i+N] == 0) cnt++; if(V[i] == 1) cnt++; } printf("%d\n",cnt); for(int i=1;i<=N;i++){ if(V[i+N] == 0) printf("%d -\n",i); if(V[i] == 1) printf("%d +\n",i); } } return 0;}
转载地址：http://inwji.baihongyu.com/