相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1934
神犇题解:http://www.cnblogs.com/Tunix/p/4337330.html
解题报告
网上都说这题简单,然而我怎么一点都不觉得啊QAQ
做题的时候,认定是最小割,然而怎么都建不出图
一直想搞成二分图,然而一直搞不成
最后看了题解
感觉这题还是相当不错的!
先假设每一个人都按照原始意图进行了选择
然后再来最小化冲突
具体到建图,可以把赞同的连到S,不赞同的连到T
朋友之间连双向边,因为朋友可能会变卦
这么建图有一个非常形象的理解:
最后和S相连的就是最后赞同的,最后和T相连的就是否决的
那么对于S->T的一条路径:
要么冲突+1,即割掉朋友间的那条边
要么其中一人改变选择,即割掉两侧的边
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300+9; const int M = N*N*2; const int INF = 10000000; int head[N],nxt[M],to[M],flow[M],n,m,dis[N],S,T,cur[N]; queue<int> que; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void Add_Edge(int u, int v, int f) { static int TT = 1; to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = f; } inline bool BFS(){ memset(dis,-1,sizeof(dis)); dis[S] = 0; que.push(S); while (!que.empty()) { int w = que.front(); que.pop(); for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) dis[to[i]] = dis[w] + 1, que.push(to[i]); } return ~dis[T]; } int DFS(int w, int f) { if (w == T) return f; else { int ret = 0; for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) { int tmp = DFS(to[i], min(f, flow[i])); ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp; if (!f) break; } return ret; } } inline int Dinic(){ int ret = 0; while (BFS()) { memcpy(cur,head,sizeof(head)); ret += DFS(S,INF); } return ret; } int main(){ n = read(); m = read(); S = 0; T = n+1; for (int i=1;i<=n;i++) if (!read()) Add_Edge(S,i,1); else Add_Edge(i,T,1); for (int i=1,a,b;i<=m;i++) a = read(), b = read(), Add_Edge(b,a,1); printf("%d\n",Dinic()); return 0; }
—————————— UPD 2017.7.4 ——————————
好像这题是挺简单的