[SHOI2007]善意的投票

Description:

幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。

我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？

Hint:

2≤n≤300，1≤m≤n(n-1)/2。

Solution:

投1和投0分别代表要划分成的两个集合,这种问题一般用最小割解决了

直接把S和T分别连向每个人开始的意愿,流量为1,割掉代表违背自己意愿的代价

同时朋友之间连双向边代表一种传递关系,流量为1,割掉代表冲突数

跑最大流就好了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const ll mxn=1e5+5,inf=1e17;
ll a1,a2,b1,b2,an,bn,c0,c1,s0,s1,n,m,cnt,ans,hd[mxn];
ll a[555],col[55][55];
ll dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};
char mp[500][500];

inline ll read() {
    char c=getchar(); ll x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(ll &x,ll y) {if(xy) x=y;}

struct ed {
    ll to,nxt,w;
}t[mxn<<1];

inline void add(ll u,ll v,ll w) {
    t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
    t[++cnt]=(ed) {u,hd[v],0}; hd[v]=cnt;
}

ll S,T,cur[mxn],dep[mxn];

ll bfs() {
    memset(dep,0,sizeof(dep)); dep[S]=1;
    queue q; q.push(S); 
    for(ll i=S;i<=T;++i) cur[i]=hd[i];
    while(!q.empty()) {
        ll u=q.front(); q.pop();
        for(ll i=hd[u];i!=-1;i=t[i].nxt) {
            ll v=t[i].to;
            if(!dep[v]&&t[i].w>0) 
                dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[T];
}

ll dfs(ll u,ll f) {
    if(u==T) return f;
    for(ll &i=cur[u];i!=-1;i=t[i].nxt) {
        ll v=t[i].to;
        if(t[i].w>0&&dep[v]==dep[u]+1) {
            ll tp=dfs(v,min(f,t[i].w));
            if(tp>0) {
                t[i].w-=tp;
                t[i^1].w+=tp;
                return tp;
            }
        }
    }
    return 0;
} 

void Dinic() {
    while(bfs()) 
        while(ll tp=dfs(S,inf)) 
            ans+=tp;
}

int main() 
{
    n=read(); m=read(); int u,v;
	memset(hd,-1,sizeof(hd)); T=n+m+1;
	for(int i=1;i<=n;++i) {
		a[i]=read();
		if(a[i]) add(S,i,1);
		else add(i,T,1);
	}
	for(int i=1;i<=m;++i) {
		u=read(); v=read();
		add(u,v,1); add(v,u,1);
	}
	Dinic(); printf("%lld",ans);
	return 0;
}

网络流

[SHOI2007]善意的投票

Description:

Hint:

Solution:

相关

图论---网络流

网络流学习笔记

Codeforces 1373F - Network Coverage（模拟网络流）

网络流24题-骑士共存

【网络流24题】最长不下降子序列问题

网络流各算法超详细带源码解析

python 方法无法在线程中使用（附python获取网络流量）

[教程]网络流详解: 从入门到放弃

网络流基础知识

网络流（二）

[知识点]网络流基础

【网络流】CF708D Incorrect Flow

标签