SPOJ1693 COCONUTS - Coconuts-白红宇

SPOJ1693 COCONUTS - Coconuts

阅读量：6162 次

发布时间：2019-06-21

本文共 1747 字，大约阅读时间需要 5 分钟。

[洛谷]

自闭QAQ 什么玩意QAQ

不是很理解到底在干啥问了巨佬以后大概是这个样子的

可以看出是最小割模型

对于每一个人反悔的话就是代价+1

那么连接(s,i) (i,t)分别表示他最后选择赞同还是反对

根据初始状态来填代价

然后针对基友关系他们之间连代价为1的无向边

为什么是无向边呢是因为他们无论双方在哪个方向反对只要不属于同一边的话就是有代价的

Edelweiss的PDF里还有这样的一个小补充

对于求一个函数 $\sum |1-x_i|*|p_i-v_0| +\sum x_i *|p_i-v_1| +\sum |x_i-x_j| *|p_i-p_j|$ 的最小值（其中 $x_i \epsilon \{0,1\}$ ）

对于（二者取其一）（不同有代价）这样的模型我们也可以用类似的方法建立最小割来求解

比较有趣。附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 20021225#define ll long long#define mxm 360010#define mxn 310using namespace std;struct edge{int to,lt,f;}e[mxm];int in[mxn],s,t,cnt=1,dep[mxn];void add(int x,int y,int f){	e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].f=f;in[x]=cnt;	e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].f=0;in[y]=cnt;}queue
         
           que;bool bfs(){ memset(dep,0,sizeof(dep)); dep[s]=1;while(!que.empty()) que.pop(); que.push(s); while(!que.empty()) { int x=que.front();que.pop(); for(int i=in[x];i;i=e[i].lt) { int y=e[i].to;if(dep[y]||!e[i].f) continue; dep[y]=dep[x]+1;que.push(y); if(y==t) return true; } } return false;}int dfs(int x,int flow){ if(x==t||!flow) return flow; int cur=flow; for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(dep[y]==dep[x]+1&&e[i].f) { int tmp=dfs(y,min(e[i].f,cur)); cur-=tmp;e[i].f-=tmp;e[i^1].f+=tmp; if(!cur) return flow; } } dep[x]=-1;return flow-cur;}int dinic(){ int ans=0; while(bfs()) ans+=dfs(s,inf); return ans;}int main(){ int n,m,x,y; while(scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; s=n+1;t=s+1; memset(in,0,sizeof(in)); cnt=1; for(int i=1;i<=n;i++) { scanf("%d",&x); if(x) add(s,i,1),add(i,t,0); else add(s,i,0),add(i,t,1); } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y,1);add(y,x,1); } printf("%d\n",dinic()); } return 0;}