题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2768
题意：同 BZOJ 1934 [Shoi2007]Vote 善意的投票
时隔一个月后才做到的双倍经验题... 感觉还是挺有趣的
别说会做了... 之前的自己连这么裸的建图都不理解... 蒟蒻认为网络流建模需要一个系统的思路，下面简单说一下自己的思路
首先看到原题，题意可以抽象成：对于每个点有两个 决策 ，每个决策会带来一定的 代价 ，求最小总代价。
通过流量限定决策，通过费用限定代价 是很显然的费用流模型，所以可以朴素的向费用流考虑，然而此题有一个特殊的性质——代价和决策都是非 0 即 1 的，所以费用和流量实际上没有区别，可以最小割解决，只需要考虑 决策 ，不需要考虑 代价 。
具体怎么搞呢？首先最小割跑完后的残量网络一定是我们希望的决策状态，如果没有朋友关系这个限定，显然直接给每个人分配自己所喜欢的即可了，这样的图一定是不连通的，根据自己喜欢的是 1 还是 0 分别连向 S 和 T，这就是在不考虑朋友关系下的状态。现在我们考虑朋友关系，一组朋友关系的实质其实是让两个人存在矛盾，把两个人连起来了，即可能导致存在 S-T 的通路。那么可以在两个人之间连一条无向边。这样建立的新图 S-T 是连通的，我们考虑通过 决策 来使得 S-T 回到不连通的理想状态——最小割。
那么回到问题，我们有什么可选的 决策 呢？如果我们目前的决策均能在建出的图中正确的抽象出来，那么这个建图就是正确的了，否则针对性的修改即可。首先我们可以让两个矛盾的朋友中的一个选择自己不喜欢的那个，即割掉一条 (S,i)/(T,i)，显然原图不连通，或者可以接受这对矛盾关系，即不改变选项，割点朋友间的无向边，这样也是合法的 决策 。
当我们满足了整道题的所有 可能决策 和 代价 后，建模就正确啦！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 310 #define M 100000 #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans; int tmp,u,v,n,m,S,T; struct zgz { int next,to,val; }edge[M]; int cnt=2,head[M]; void add(int from,int to,int val) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } void ins(int from,int to,int val) {add(from,to,val);add(to,from,0);} queue<int> q; int d[N]; bool bfs() { memset(d,0,sizeof(d)); d[S]=1,q.push(S); while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(!d[to]&&val) { d[to]=d[x]+1; q.push(to); } } } return d[T]; } int dfs(int x,int v) { if(x==T||v==0)return v; int ret=0; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(d[to]==d[x]+1) { int f=dfs(to,min(val,v)); edge[i].val-=f,edge[i^1].val+=f; v-=f,ret+=f; if(v==0)break; } } if(ret==0)d[x]=-1; return ret; } int main() { n=read(),m=read();S=0,T=n+1; for(int i=1;i<=n;i++) { tmp=read(); if(tmp)ins(S,i,1); else ins(i,T,1); } for(int i=1;i<=m;i++) { u=read(),v=read(); add(u,v,1),add(v,u,1); } while(bfs())ans+=dfs(S,inf); printf("%d",ans); } |
Comments | NOTHING