【bzoj2768】【JLOI2010】【冠军调查】【最小割】
发布日期:2021-11-16 15:38:24 浏览次数:4 分类:技术文章

本文共 2246 字,大约阅读时间需要 7 分钟。

Description

一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰,英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查,调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者,大家齐聚一堂,各抒己见。每一位参与者都将发言,阐述自己的看法。参与者的心里都有一个看法,比如FireDancer认为切尔西不可能夺冠,而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友,所以可能FireDancer为了迁就自己的好朋友,会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网,希望你能安排每个人的发言内容,使得违心说话的人的总数与发言时立场不同的朋友(对)的总数的和最小。
 

Input

第一行两个整数n和m,其中n(2≤n≤300)表示参与者的总数,m(0≤m≤n(n-1)/2)表示朋友的总对数。
第二行n个整数,要么是0要么是1。如果第i个整数的值是0的话,表示第i个人心里认为切尔西将与冠军无缘,如果是1的话,表示他心里认为切尔西必将夺魁。
下面m行每行两个不同的整数,i和j(1≤i, j≤n)表示i和j是朋友。注意没有一对朋友会在输入中重复出现。朋友关系是双向的,并且不会传递。
 

Output

 
只有一个整数,为最小的和。

Sample Input

3 3
1 0 0
1 2
1 3
2 3

Sample Output

1

HINT

最好的安排是所有人都在发言时说切尔西不会夺冠。这样没有一对朋友的立场相左,只有第1个人他违心说了话。

题解:源点向每个初始立场为1的人连权值为1的边。

         每个初始立场为0的人向汇点连权值为1的边。

         好朋友之间互相连权值为1的边。

        最小割即是答案。

代码:

#include
#include
#include
#include
#define M 1001001#define N 310#define INF 2100000000using namespace std;struct use{int st,en,v;}e[M];int point[N],next[M],n,a[N],s,cnt(1),x,y;int cur[N],pre[N],dis[N],gap[N],st,en,m;void add(int x,int y,int v){ next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;e[cnt].v=v; next[++cnt]=point[y];point[y]=cnt;e[cnt].st=y;e[cnt].en=x;e[cnt].v=0; }int isap(){ int ans(0),minn,i,u;bool f=false;gap[0]=en-st+1;u=st; for (int i=st;i<=en;i++) cur[i]=point[i]; while (dis[st]<=en-st+1){ f=false; for (i=cur[u];i;i=next[i]) if(e[i].v&&dis[u]==dis[e[i].en]+1){cur[u]=i;f=true;break;} if (f){ u=e[i].en;pre[u]=i; if (u==en){ minn=INF; for (int i=en;i!=st;i=e[pre[i]].st)minn=min(minn,e[pre[i]].v); ans+=minn; for (int i=en;i!=st;i=e[pre[i]].st)e[pre[i]].v-=minn,e[pre[i]^1].v+=minn; u=st; } } else{ --gap[dis[u]];if (!gap[dis[u]]) return ans; minn=en-st+1; for (int i=point[u];i;i=next[i]) if (e[i].v) minn=min(minn,dis[e[i].en]); dis[u]=minn+1;gap[dis[u]]++;cur[u]=point[u];if (u!=st)u=e[pre[u]].st; } } return ans;}int main(){ scanf("%d%d",&n,&m);st=1;en=n+2; for (int i=1;i<=n;i++){ scanf("%d",&x); if (x==1) add(st,i+1,1); else add(i+1,en,1); } for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x+1,y+1,1);add(y+1,x+1,1);} printf("%d\n",isap());}

转载地址:https://blog.csdn.net/sunshinezff/article/details/50999326 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj2561】【最小生成树】【最小割】
下一篇:【bzoj1391】【Ceoi2008】【Order】【最小割】

发表评论

最新留言

很好
[***.229.124.182]2024年03月20日 03时48分40秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

easyui datagrid 中怎么选中所有页面的数据_学会这5个Excel中常用技巧,可以准时下班去摆摊了... 2019-04-21
maskrcnn还可以加网络吗_绿茶加蜂蜜的功效,绿茶可以加蜂蜜吗? 2019-04-21
marquee滚动起始位置_巧用喵影关键帧制作滚动水印,让视频小偷无可盗 2019-04-21
css 旋转45_CSS教程——第14期 2019-04-21
rust火箭基地主楼开启方法_Rust 为什么能成为 Stack Overflow 最受欢迎的语言? 2019-04-21
全年营业额怎么计算_门店盈亏平衡计算及案例分析 | 商品管理 2019-04-21
卡尔曼_卡尔曼估计两步法 2019-04-21
区域转换为二值图像_Matlab图像处理系列教程(一) 2019-04-21
字符串是单一字符的无序组合吗_Python学习笔记(八)组合数据类型 2019-04-21
从当前元素继续寻找_云漫圈 | 寻找无序数组的第k大元素 2019-04-21
控制是否展示_现场展示板管理不在于看,而在于管! 2019-04-21
pe下找不到ssd硬盘_【进入pe系统后认不到硬盘解决方法】进入pe系统看不到硬盘_pe系统不认硬盘... 2019-04-21
windows 禁用ipv6服务_在 Windows 7 中禁用IPv6协议/IPv6隧道 2019-04-21
pip 设置超时时间_Python pip使用超时问题解决方案 2019-04-21
python定义一个_Python,包括定义一个类 2019-04-21
moore 数据集_警报数据集(alarm dataset)_机器学习_科研数据集 2019-04-21
go语言io reader_go语言之IO操作(待补充) 2019-04-21
mysql 固定符号分列显示_MySql中指定符号分割并分行展示 2019-04-21
mysql 5.5 免安装_mysql 5.5.56免安装版配置方法 2019-04-21
连接不上mysql 1045_技术分享 | MySQL 客户端连不上(1045 错误)原因全解析 2019-04-21