BZOJ 2768 [JLOI2010] 冠军调查

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2768

题意：同 BZOJ 1934 [Shoi2007]Vote 善意的投票

时隔一个月后才做到的双倍经验题... 感觉还是挺有趣的

别说会做了... 之前的自己连这么裸的建图都不理解... 蒟蒻认为网络流建模需要一个系统的思路，下面简单说一下自己的思路

首先看到原题，题意可以抽象成：对于每个点有两个决策，每个决策会带来一定的代价，求最小总代价。

通过流量限定决策，通过费用限定代价 是很显然的费用流模型，所以可以朴素的向费用流考虑，然而此题有一个特殊的性质——代价和决策都是非 0 即 1 的，所以费用和流量实际上没有区别，可以最小割解决，只需要考虑决策，不需要考虑代价。

具体怎么搞呢？首先最小割跑完后的残量网络一定是我们希望的决策状态，如果没有朋友关系这个限定，显然直接给每个人分配自己所喜欢的即可了，这样的图一定是不连通的，根据自己喜欢的是 1 还是 0 分别连向 S 和 T，这就是在不考虑朋友关系下的状态。现在我们考虑朋友关系，一组朋友关系的实质其实是让两个人存在矛盾，把两个人连起来了，即可能导致存在 S-T 的通路。那么可以在两个人之间连一条无向边。这样建立的新图 S-T 是连通的，我们考虑通过决策来使得 S-T 回到不连通的理想状态——最小割。

那么回到问题，我们有什么可选的决策呢？如果我们目前的决策均能在建出的图中正确的抽象出来，那么这个建图就是正确的了，否则针对性的修改即可。首先我们可以让两个矛盾的朋友中的一个选择自己不喜欢的那个，即割掉一条 (S,i)/(T,i)，显然原图不连通，或者可以接受这对矛盾关系，即不改变选项，割点朋友间的无向边，这样也是合法的决策。

当我们满足了整道题的所有 可能决策 和代价后，建模就正确啦！

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 310
#define M 100000
#define inf 1000000000
#define ll long long
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
int ans;
int tmp,u,v,n,m,S,T;
struct zgz
{
	int next,to,val;
}edge[M];
int cnt=2,head[M];
void add(int from,int to,int val)
{
	edge[cnt].to=to;
	edge[cnt].val=val;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}
void ins(int from,int to,int val)
{add(from,to,val);add(to,from,0);}
queue<int> q;
int d[N];
bool bfs()
{
	memset(d,0,sizeof(d));
	d[S]=1,q.push(S);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=edge[i].next)
		{
			int to=edge[i].to,val=edge[i].val;
			if(!d[to]&&val)
			{
				d[to]=d[x]+1;
				q.push(to);
			}
		}
	}
	return d[T];
}
int dfs(int x,int v)
{
	if(x==T||v==0)return v;
	int ret=0;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to,val=edge[i].val;
		if(d[to]==d[x]+1)
		{
			int f=dfs(to,min(val,v));
			edge[i].val-=f,edge[i^1].val+=f;
			v-=f,ret+=f;
			if(v==0)break;
		}
	}
	if(ret==0)d[x]=-1;
	return ret;
}
int main()
{
	n=read(),m=read();S=0,T=n+1;
	for(int i=1;i<=n;i++)
	{
		tmp=read();
		if(tmp)ins(S,i,1);
		else ins(i,T,1);
	}
	for(int i=1;i<=m;i++)
	{
		u=read(),v=read();
		add(u,v,1),add(v,u,1);
	}
	while(bfs())ans+=dfs(S,inf);
	printf("%d",ans);
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 310

#define M 100000

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int ans;

int tmp,u,v,n,m,S,T;

struct zgz

{

int next,to,val;

}edge[M];

int cnt=2,head[M];

void add(int from,int to,int val)

{

edge[cnt].to=to;

edge[cnt].val=val;

edge[cnt].next=head[from];

head[from]=cnt++;

}

void ins(int from,int to,int val)

{add(from,to,val);add(to,from,0);}

queue<int> q;

int d[N];

bool bfs()

{

memset(d,0,sizeof(d));

d[S]=1,q.push(S);

while(!q.empty())

{

int x=q.front();q.pop();

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(!d[to]&&val)

{

d[to]=d[x]+1;

q.push(to);

}

return d[T];

}

int dfs(int x,int v)

{

if(x==T||v==0)return v;

int ret=0;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(d[to]==d[x]+1)

{

int f=dfs(to,min(val,v));

edge[i].val-=f,edge[i^1].val+=f;

v-=f,ret+=f;

if(v==0)break;

}

if(ret==0)d[x]=-1;

return ret;

}

int main()

{

n=read(),m=read();S=0,T=n+1;

for(int i=1;i<=n;i++)

{

tmp=read();

if(tmp)ins(S,i,1);

else ins(i,T,1);

}

for(int i=1;i<=m;i++)

{

u=read(),v=read();

add(u,v,1),add(v,u,1);

}

while(bfs())ans+=dfs(S,inf);

printf("%d",ans);

}

zgz233

zgz233

BZOJ 2768 [JLOI2010] 冠军调查

l1ll5

Comments | NOTHING