Y国有N座城市，并且有M条双向公路将这些城市连接起来，并且任意两个城市至少有一条路径可以互达。
Y国的国王去世之后，他的两个儿子A和B都想成为新的国王，但他们都想让这个国家更加安定，不会用武力解决问题。
于是他们想将这个国家分成两个小国家A国和B国。现在，A拥有1号城市，B拥有N号城市，其他的城市还尚未确定归属哪边（划分之后的国家内部城市可以不连通）。
由于大家都想让国家变得更好，而某些城市的人民愿意国王的A儿子作为他们的领袖，而某些城市更看好B，而为了交通的便捷，如果划分后的公路连接两个同一个国家的城市，那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制，具体如下：
1. 对于城市i，如果它划分给A国，将得到VA[i]的得分；划分给B国，将得到VB[i]的得分。
2. 对于一条公路i，如果它连接两个A国的城市，将得到EA[i]的得分；连接两个B国的城市，将得到EB[i]的得分；否则，这条公路将失去意义，将扣除EC[i]的得分。
现请你找到最优的土地划分，使得这种它的评分最高。
第一行包含两个整数N，M，含义如问题描述所示。
接下来一行N-2个非负整数，表示VA[2..N-1]。
接下来一行N-2个非负整数，表示VB[2..N-1]。
接下来M行，每行五个非负整数描述一条公路：X Y EA[i] EB[i] EC[i]，含义如问题描述所示。
输出有且仅有一个整数，表示最高评分。
【数据说明】
数据点 N M 备注
1-2 <=20 <=200 无
3-4 <=5000 <=10000 VA、VB、EA、EB均为0
5-6 <=5000 <=10000 EC均为0
7-10 <=10000 <=40000 无
保证运算过程中及最终结果不超过32位带符号整数类型的表示范围
二者必取其一，这个很有最小割的意思，所以相当于将A国是源点，B国为汇点
对于一个点$P_i$，设其分到A国的价值为$V_{ai}$，分到B国的价值为$V_{bi}$。
取A则无法取B，这就是最小割模型了。
那么从源点连向$P_{i}$一条有向边，容量为$V_{ai}$，那么从$P_i$向汇点一条有向边，容量为$V_{bi}$，
这样点的二选一就实现了，只需要用$\sum{V_{ai}+V_{bi}}$减去最小割就可以啦。
下面是边的三选一：(设一条边连A国城市贡献为$C_{ai}$,连B国城市贡献为$C_{bi}$，连接两个国家点惩罚为$C_{ci}$）
两个点若都选A，那么就需要割去这条边连接B国两个城市点贡献。
选A相当于割去城市选B国点贡献，那么相当于在汇点端取消了流量。
那么现在限制一下，要求其取消汇点端流量则必须取消这条边流量。
那么就相当于在原来两个城市向汇点连边处向汇点重新连边。
由于两个点都必须限制，那么相当于在两个点都向汇点连$\frac{C_{bi}}{2}$的边。
同理从源点连向边的两端点$\frac{C_{ai}}{2}$的边。
所以在答案上加上$\sum{C_{ai}+C_{bi}}$最后减去最小割。
考虑惩罚条件。
此时为边的两端一个割源，一个割汇。
此时为了保证出现割，保留与汇点连边端必须断开所有与源点连边。
所以此时最小割中一定存在$\frac{C_{ai}}{2}$，也就是这条边存在时与源点的附加边。
同理，最小割中也存在$\frac{C_{bi}}{2}$，这样割下来的代价为$\frac{C_{bi}}{2}+\frac{C_{ai}}{2}$
但是我们期望其扣除的代价为$C_{ai}+C_{bi}+C_{ci}$，这就要求我们同时要割下一条代价为$\frac{C_{bi}}{2}+\frac{C_{ai}}{2}+C_{ci}$的边。
可是这条边应该加在哪里呢。
考虑什么样的边一定被割掉，一定是当前存在的与源点连边的点连向一个与汇点有流量的点。
那么就是在当前边两端对应的点间加一双向边，边权为$\frac{C_{bi}}{2}+\frac{C_{ai}}{2}+C_{ci}$。
证明这样做的可行性。
因为当两端选同一个国家时，中间的流量不会流向汇或不会与源有流量。
所以这条附加边在两端选同一国家时是不会存在流量的，更不会被割去。
所以建图就是这样了。
因为有系数$\frac{1}{2}$的存在，将所有边权*2，最后/2，可以证明最后一定是整除的，没有必要担心。
全图最小割就好了。
代码：
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 const int oo=0x3f3f3f3f; 6 struct pnt{ 7 int hd; 8 int lyr; 9 int now; 10 }p[100000]; 11 struct ent{ 12 int twd; 13 int lst; 14 int vls; 15 }e[1000000]; 16 int cnt; 17 int n,m; 18 int s,t; 19 std::queue<int>Q; 20 void ade(int f,int t,int v) 21 { 22 cnt++; 23 e[cnt].twd=t; 24 e[cnt].vls=v; 25 e[cnt].lst=p[f].hd; 26 p[f].hd=cnt; 27 return ; 28 } 29 bool Bfs(void) 30 { 31 while(!Q.empty()) 32 Q.pop(); 33 for(int i=1;i<=t;i++) 34 p[i].lyr=0; 35 p[s].lyr=1; 36 Q.push(s); 37 while(!Q.empty()) 38 { 39 int x=Q.front(); 40 Q.pop(); 41 for(int i=p[x].hd;i;i=e[i].lst) 42 { 43 int to=e[i].twd; 44 if(p[to].lyr==0&&e[i].vls>0) 45 { 46 p[to].lyr=p[x].lyr+1; 47 if(to==t) 48 return true; 49 Q.push(to); 50 } 51 } 52 } 53 return false; 54 } 55 int Dfs(int x,int fll) 56 { 57 if(x==t) 58 return fll; 59 for(int& i=p[x].now;i;i=e[i].lst) 60 { 61 int to=e[i].twd; 62 if(p[to].lyr==p[x].lyr+1&&e[i].vls>0) 63 { 64 int ans=Dfs(to,std::min(fll,e[i].vls)); 65 if(ans>0) 66 { 67 e[i].vls-=ans; 68 e[((i-1)^1)+1].vls+=ans; 69 return ans; 70 } 71 } 72 } 73 return 0; 74 } 75 int Dinic(void) 76 { 77 int ans=0; 78 while(Bfs()) 79 { 80 for(int i=1;i<=t;i++) 81 p[i].now=p[i].hd; 82 int dlt; 83 while(dlt=Dfs(s,oo)) 84 ans+=dlt; 85 } 86 return ans; 87 } 88 int main() 89 { 90 // freopen("a.in","r",stdin); 91 scanf("%d%d",&n,&m); 92 s=n+1; 93 t=s+1; 94 int ans=0; 95 ade(s,1,oo); 96 ade(1,s,0); 97 ade(n,t,oo); 98 ade(t,n,0); 99 for(int i=2;i<=n-1;i++) 100 { 101 int x; 102 scanf("%d",&x); 103 x<<=1; 104 ade(s,i,x); 105 ade(i,s,0); 106 ans+=x; 107 } 108 for(int i=2;i<=n-1;i++) 109 { 110 int x; 111 scanf("%d",&x); 112 x<<=1; 113 ade(i,t,x); 114 ade(t,i,0); 115 ans+=x; 116 } 117 for(int i=1;i<=m;i++) 118 { 119 int x,y,a,b,c; 120 scanf("%d%d%d%d%d",&x,&y,&a,&b,&c); 121 ans+=a+b+a+b; 122 ade(s,x,a); 123 ade(x,s,0); 124 ade(s,y,a); 125 ade(y,s,0); 126 ade(x,t,b); 127 ade(t,x,0); 128 ade(y,t,b); 129 ade(t,y,0); 130 ade(x,y,a+b+c+c); 131 ade(y,x,a+b+c+c); 132 } 133 ans=(ans-Dinic())>>1; 134 printf("%d\n",ans); 135 return 0; 136 }
原文：https://www.cnblogs.com/blog-Dr-J/p/10238258.html