P2057 善意的投票 最小割理解
2024-10-06 17:46:45
实现时这样建图:直接将S连向同意的人,T连向不同意的人,若两人是朋友,则在他们之间连一条双向边
#include<bits/stdc++.h>
#define il inline
using namespace std;
const int N=,inf=;
int n,m,s,t=,h[N],cnt=,dis[N],ans;
struct edge{
int to,net,v;
}e[N*];
il void add(int u,int v,int w)
{
e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt;
e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=,h[v]=cnt;
}
queue<int>q;
il bool bfs()
{
memset(dis,-,sizeof(dis));
q.push(s),dis[s]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].net)
if(dis[e[i].to]==-&&e[i].v>)dis[e[i].to]=dis[u]+,q.push(e[i].to);
}
return dis[t]!=-;
}
il int dfs(int u,int op)
{
if(u==t)return op;
int flow=,used=;
for(int i=h[u];i;i=e[i].net)
{
int v=e[i].to;
if(dis[v]==dis[u]+&&e[i].v>)
{
used=dfs(v,min(op,e[i].v));
if(!used)continue;
flow+=used,op-=used;
e[i].v-=used,e[i^].v+=used;
if(!op)break;
}
}
if(!op)dis[u]=-;
return flow;
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i=;i<=n;i++){
scanf("%d",&x);
if(x==)add(s,i,);
else add(i,t,);
}
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y,),add(y,x,);
}
while(bfs())ans+=dfs(s,inf);
cout<<ans;
return ;
}
最新文章
- iOS项目相关@AFN&;SDWeb的二次封装
- 1296: [SCOI2009]粉刷匠
- ASP.NET MVC学习系列(二)-WebAPI请求
- iOS 开发笔记
- js基础之动画(一)
- mfc Clistctr 单元格嵌入图片(bmp)
- Cocos2d-x优化中多线程并发访问
- WPF InkCanvas 画图 基础使用教程
- Maven “Failed to execute goal org.apache.maven.plugins:maven-archetype-plugin:2.4:create...”问题总结
- oracle分页,带有排序字段
- 用C#编写Linux守护进程
- 测试驱动开发 TDD
- Linux-02
- python基础篇_001_初识Python
- Nginx安装详细指南
- mysql命令行导入结构化数据
- 左手坐标系和右手坐标系 ZZ
- WideCharToMultiByte和MultiByteToWideChar函数的用法(转载)
- P4211[BZOJ 3626] [LNOI2014]LCA
- PHP之编写日志文件留后门(免杀)
热门文章
- 学习Yii(3)
- thinkPHP5 命名空间别名
- fatal error C1189: #error : Building MFC application with /MD[d] (CRT dll version) requires MFC sha
- storm并行度核心概念介绍剖析
- (二)Spring中的ioc
- Selenium工具爬取商品
- linux 对外开放端口
- Jmeter博文索引~基础知识和实践操作汇总
- Date及DateFormat用法
- PHP获取指定时间的前6个月月份 、获取前6天日期