网站建设各个模块的功能,微信运营技巧,电商网站建设与维护,广州品牌SP1693 COCONUTS 题意#xff1a; 几个士兵在投票#xff0c;有支持与反对两种选择#xff0c;每个人有自己的看法#xff0c;但是他们有时也会为了支持朋友的看法而放弃自己的看法#xff0c;请求出一种方案#xff0c;使得违背自己初始看法的人数与看法不一致的朋友对数…SP1693 COCONUTS 题意 几个士兵在投票有支持与反对两种选择每个人有自己的看法但是他们有时也会为了支持朋友的看法而放弃自己的看法请求出一种方案使得违背自己初始看法的人数与看法不一致的朋友对数之和最小人数不大于300。 做法 这是一道网络流的题目。是源点s代表支持汇点t代表反对最小割即所有人决策的最小代价之和。如果一个人支持则t向他连边反之他向s连边。如果有一对朋友那他们互相连边所有边权为1。然后跑最小割即可。 #includebits/stdc.h
#define rep(i,a,b) for(int i(a),i##ed(b);ii##ed;i)
#define per(i,a,b) for(int i(a),i##ed(b);ii##ed;i--)
using namespace std;
const int N1010,M2000010,INF0x3f3f3f3f;
int s,t,n,m,sum;
int cnt,hed[N],to[M],nxt[M],val[M];
int cur[M],dis[M],g[M];inline void add(int x,int y,int z) { to[cnt]y,val[cnt]z,nxt[cnt]hed[x],hed[x]cnt; }
inline int Min(int x,int y) { return xy? x:y; }
int SAP(int u,int flow) {if(ut) return flow; int vflow;for(;cur[u];cur[u]nxt[cur[u]])if(dis[to[cur[u]]]dis[u]-1val[cur[u]]) {int fSAP(to[cur[u]],Min(v,val[cur[u]]));val[cur[u]]-f,val[cur[u]^1]f,v-f;if(!v) return flow;}if(!--g[dis[u]]) dis[s]t-s2;g[dis[u]],cur[u]hed[u]; return flow-v;
}
int main() {for(;;) {scanf(%d%d,n,m); if(!n!m) break;cnt1,memset(hed,0,sizeof(hed)),s0,tn1,sum0;rep(i,1,n) {int x;scanf(%d,x);x? (add(s,i,1),add(i,s,0)):(add(t,i,0),add(i,t,1));}rep(i,1,m) {int x,y;scanf(%d%d,x,y);add(x,y,1),add(y,x,0),add(y,x,1),add(x,y,0);}rep(i,s,t) cur[i]hed[i],g[i]0,dis[i]0;for(g[0]t-s1;dis[s]t-s1;sumSAP(s,INF));printf(%d\n,sum);}return 0;
} 转载于:https://www.cnblogs.com/daniel14311531/p/10458249.html
