【洛谷2057】 [SHOI2007]善意的投票（最小割）

古城微笑少年丶 2022-01-09 07:21 215阅读 0赞

## 传送门 ##

[洛谷][Link 1]

## Solution ##

比较巧妙啊！  
考虑这个只有同意和不统一两种，所以直接令\\(s\\)表示选，\\(t\\)表示不选，然后在朋友直接建双向边就好了。

## 代码实现 ##

#include<bits/stdc++.h> using namespace std; const int N=500010,Inf=1e9+10; int front[N],cnt,s,t,n,m; struct node { int to,nxt,w; }e[1500010]; queue<int>Q; int dep[N]; inline int gi() { int sum=0,f=1;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum; } void Add(int u,int v,int w) { e[cnt]=(node){v,front[u],w};front[u]=cnt++; e[cnt]=(node){u,front[v],0};front[v]=cnt++; } bool bfs() { memset(dep,0,sizeof(dep)); Q.push(s);dep[s]=1; while(!Q.empty()) { int u=Q.front();Q.pop(); for(int i=front[u];i!=-1;i=e[i].nxt) { int v=e[i].to; if(!dep[v] && e[i].w) { dep[v]=dep[u]+1;Q.push(v); } } } return dep[t]; } int dfs(int u,int flow) { if(u==t || !flow)return flow; for(int i=front[u];i!=-1;i=e[i].nxt) { int v=e[i].to; if(dep[v]==dep[u]+1 && e[i].w) { int di=dfs(v,min(flow,e[i].w)); if(di) { e[i].w-=di;e[i^1].w+=di; return di; } else dep[v]=0; } } return 0; } int dinic() { int flow=0; while(bfs()) { while(int d=dfs(s,Inf))flow+=d; } return flow; } int main() { #ifndef ONLINE_JUDGE freopen("in.in","r",stdin); #endif memset(front,-1,sizeof(front)); n=gi();m=gi();t=n+1; for(int i=1;i<=n;i++) { int x=gi(); if(x)Add(s,i,1); else Add(i,t,1); } while(m--) { int u=gi(),v=gi(); Add(u,v,1);Add(v,u,1); } printf("%d\n",dinic()); return 0; }

转载于:https://www.cnblogs.com/mle-world/p/10555675.html

[Link 1]: https://www.luogu.org/problemnew/show/P2057

发表评论取消回复

表情：

评论列表（有 0 条评论，215人围观）

还没有评论，来说两句吧...

相关阅读

相关【洛谷】P1576 最小花费

前言文章来源：CSDN@LawsonAbs 合理时间：12min -------------------- 题目 [题目链接][Link 1]

骑猪看日落/ 2022年09月09日 09:12/ 0 赞/ 192 阅读

相关洛谷P1434 [SHOI2002]滑雪

题目描述 Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Mic

心已赠人/ 2022年05月30日 02:40/ 0 赞/ 212 阅读

相关【洛谷2057】 [SHOI2007]善意的投票（最小割）

传送门 [洛谷][Link 1] Solution 比较巧妙啊！考虑这个只有同意和不统一两种，所以直接令\\(s\\)表示选，\\(t\\)表示不选，然后在

古城微笑少年丶/ 2022年01月09日 07:21/ 0 赞/ 216 阅读

相关 luoguP2057善意的投票

理解下题意：题意大致就是有n个人有两种不同的意见并且有许多朋友，需要让朋友间尽可能的统一意见（少发生冲突），如果一个人违反自己的本意也算冲突，求最少的冲突。。。思

谁践踏了优雅/ 2021年12月23日 01:35/ 0 赞/ 266 阅读

相关 [洛谷P2057][SHOI2007]善意的投票

题目大意：有$n(n\\leqslant300)$个人，每个人可以选择$0$或$1$，每个人最开始有意愿，有$m(m\\leqslant\\dfrac\{n(n-1)\}2)$

古城微笑少年丶/ 2021年12月22日 04:15/ 0 赞/ 235 阅读

相关洛谷P3388 模板割点

题目链接：[https://www.luogu.org/problemnew/show/P3388][https_www.luogu.org_problemnew_show_P

妖狐艹你老母/ 2021年12月10日 23:09/ 0 赞/ 258 阅读

相关最小生成树 & 洛谷P3366【模板】最小生成树 & 洛谷P2820 局域网

嗯... 理解生成树的概念：在一幅图中将所有n个点连接起来的n-1条边所形成的树。最小生成树：边权之和最小的生成树。最小瓶颈生成树

迈不过友情╰/ 2021年12月10日 20:03/ 0 赞/ 323 阅读

相关【洛谷 3388】割点

题目背景割点题目描述给出一个nnn个点，mmm条边的无向图，求图的割点。输入输出格式输入格式：第一行输入n,mn,mn,m 下面mm

水深无声/ 2021年10月26日 21:46/ 0 赞/ 319 阅读

相关【洛谷 1576】最小花费

题目描述在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得

ゝ一纸荒年。/ 2021年10月20日 00:56/ 0 赞/ 304 阅读

相关【洛谷P3388】【模板】割点

都快忘了割点怎么搞了对所有点分两类 1.根节点 2.非根节点显然根节点是很好做的只需要数一下有没有两个子树以上对于非根节点利用tarjan算法回忆到dfn

Dear 丶/ 2021年09月29日 23:10/ 0 赞/ 381 阅读