bzoj1934：[shoi2007]善意的投票&bzoj2768：[jloi2010]冠军调查——题解(代码片段)

关键词：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=350;
const int M=N*N+N;
const int INF=1e9;
inline int read()
    int X=0,w=0;char ch=0;
    while(!isdigit(ch))w|=ch==\'-\';ch=getchar();
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;

struct node
    int nxt,to,w;
edge[M];
int head[N],cnt=-1,S,T;
void add(int u,int v,int w)
    edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt;

int lev[N],cur[N],dui[N];
bool bfs(int m)
    int r=0;
    for(int i=1;i<=m;i++)
    lev[i]=-1;
    cur[i]=head[i];
    
    dui[0]=S,lev[S]=0;
    int u,v;
    for(int l=0;l<=r;l++)
    u=dui[l];
    for(int e=head[u];e!=-1;e=edge[e].nxt)
        v=edge[e].to;
        if(edge[e].w>0&&lev[v]==-1) 
        lev[v]=lev[u]+1;
        r++;
        dui[r]=v; 
        if(v==T)return 1; 
        
    
    
    return 0;

int dinic(int u,int flow,int m)
    if(u==m)return flow;
    int res=0,delta;
    for(int &e=cur[u];e!=-1;e=edge[e].nxt)
    int v=edge[e].to;
    if(edge[e].w>0&&lev[u]<lev[v]) 
        delta=dinic(v,min(edge[e].w,flow-res),m); 
        if(delta>0)
        edge[e].w-=delta;
        edge[e^1].w+=delta;
        res+=delta;
        if(res==flow)break; 
        
    
    
    if(res!=flow)lev[u]=-1;
    return res;

int c[N];
int main()
    memset(head,-1,sizeof(head));
    int n=read(),m=read();
    S=n+1,T=S+1;
    for(int i=1;i<=n;i++)
    if(c[i]=read())add(S,i,1),add(i,S,0);
    else add(i,T,1),add(T,i,0);
    
    for(int i=1;i<=m;i++)
    int a=read(),b=read();
    if(c[b])swap(a,b);
    add(a,b,1),add(b,a,0);
    
    int ans=0;
    while(bfs(T))ans+=dinic(S,INF,T);
    printf("%d\\n",ans);
    return 0;

bzoj1934:[shoi2007]vote善意的投票

题目链接bzoj1934:[Shoi2007]Vote善意的投票题解睡觉作为源点，不睡作为汇点对于一个人违背自己的意愿，连向与自己意愿相反的源汇，容量为1对于朋友意见相反，在朋友之间连容量为2的双向边，切得时候双向边使得该边漫流求一... 查看详情

bzoj-1934:[shoi2007]vote善意的投票(网络流最小割)

1934:[Shoi2007]Vote善意的投票TimeLimit: 1Sec  MemoryLimit: 64MBSubmit: 2353  Solved: 1470[​​Submit​​​][​​Status​​​][​​Discuss​​]Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对 查看详情

bzoj-1934:[shoi2007]vote善意的投票(网络流最小割)

1934:[Shoi2007]Vote善意的投票TimeLimit: 1Sec  MemoryLimit: 64MBSubmit: 2353  Solved: 1470[Submit][Status][Discuss]Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重 查看详情

bzoj1934[shoi2007]vote善意的投票（最小割）

 【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1934 【题目大意】　　每个人对于投票都有自己原来的观点：1或者0，　　他可以违背自己原来的意愿投相反的票，　　同时存在一些相互的朋友关系，　　我们定义... 查看详情

bzoj1934:[shoi2007]vote善意的投票

最大流。。建图方式都是玄学啊。。//Dinic是O(n2m)的。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>usingnamespacestd;#definerep(i,s,t)for(inti=s;i<=t;i++)#definedwn(i,s,t)f 查看详情

bzoj1934:[shoi2007]vote善意的投票

get到新姿势，最小割=最大流，来个大佬的PPT这道题的做法是将st和1的xpy连，0的xpy和ed连，xpy之间jy连双向边，然后呢答案就是最小割。#include<cstdio>#include<iostream>#include<cstring>usingnamespacestd;structnode{intx,y,c,next,other;}a[11... 查看详情

bzoj1934[shoi2007]vote善意的投票

我大概是把自己水废掉了。第一眼匈牙利？不知道怎么想到的，然后发现不可做。似乎是网络流呀。看了半天硬是没把图建出来。出去冷静一下。wc这不是和文理分科那啥一模一样嘛，还简单得多。。。我是zz，鉴定完毕。//Twenty... 查看详情

bzoj1934：[shoi2007]善意的投票&bzoj2768：[jloi2010]冠军调查——题解(代码片段)

https://www.lydsy.com/JudgeOnline/problem.php?id=1934https://www.lydsy.com/JudgeOnline/problem.php?id=2768幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的... 查看详情

bzoj1934

　　1934:[Shoi2007]Vote善意的投票TimeLimit: 1Sec  MemoryLimit: 64MBSubmit: 2406  Solved: 1498[Submit][Status][Discuss]Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是 查看详情

bzoj1934--善意的投票(最小割)

　　　　。。。题目链接：　　　　http://www.lydsy.com/JudgeOnline/problem.php?id=1934 Solution　　　　小朋友的冲突就是割，然后这道题要求的就是最小的割。。。　　　　从源点向刚开始为1的点连边，从每个刚开始为0的点向汇点连... 查看详情

[shoi2007]善意的投票(代码片段)

[题目链接]      https://www.lydsy.com/JudgeOnline/problem.php?id=1934[算法]    首先，选择睡觉的人和不选择睡觉的人构成两个集合    这启发我们用最小割解决该问题:    1.将... 查看详情

bzoj1934善意的投票(最小割)

把人分成两个集合，一个赞成睡觉，一个反对睡觉。好朋友连一条容量为1的双向边，s向赞成睡觉的连边，反对睡觉的向t连边。那么这个图的一个割就对应着一个方案。如果割掉s和v的边，就代表v投意见与它自己相反的票，t和v... 查看详情

「shoi2007」「codevs2341」善意的投票(代码片段)

2341善意的投票2007年省队选拔赛上海市队选拔赛时间限制:5s空间限制:128000KB题目等级:大师Master 题目描述Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬... 查看详情

p2057[shoi2007]善意的投票(最小割)(代码片段)

P2057[SHOI2007]善意的投票(最小割)同意与非同意建立S-T。然后S连同意的人，T连不同意的人。好朋友之间连双向边。连双向边的原因是关系之间是双向，且可能发生同阵营的人之间是好朋友。然后跑最大流最小割即可。#includ... 查看详情

shoi2007善意的投票(代码片段)

题目链接：戳我这个题一开始看到数据范围和只能选0或者1的时候，直接就想到了网络流......可是想到费用流上了。但是之后发现这个题并不能用费用流做。因为虽然代价可以转化成费用，但是流量并不是可以确定限制的。先把... 查看详情

[shoi2007]善意的投票(代码片段)

嘟嘟嘟 看数据范围，加上题中频繁提到的冲突，就可以想到算法是最小割。1.同意睡觉的，源点就像他连一条容量为1的边。割掉它就代表他背叛了自己的意愿。2.同理，不同意睡觉的，就像汇点连一条边。3.考虑每一对朋友... 查看详情

p2057[shoi2007]善意的投票(代码片段)

传送门分析权值不同点之间连权值为1的边起点向每个1，每个0向终点也连权值为1的边跑最小割即可代码#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cctype>#include<cmath>#incl... 查看详情

[shoi2007]善意的投票(代码片段)

直接是最小割啊设最终还和(S)相连表示睡觉，和(T)相连表示不睡觉如果这个人想睡觉，那么就从源点向它连(1)的边，表示割掉这条边选择不睡觉的代价为1如果这个人不想睡觉的话，就向汇点连一条(1)的边，表示选择睡觉的代价... 查看详情