Beyond the Void
BYVoid
USACO 5.4.5 TeleCowmunication 奶牛的电信 telecow

算法和4.4的pollutant control(求最小边割集)类似,但这道题是求最小点割集。

我们可以把每个点i拆成两个点i1,i2,这两个点之间建立一条边权为1的有向弧。对于原图中边(i,j),建立(i2,j1)和(j2,i1)两条边权为∞的有向弧。这样就把求最小点割转化成了求最小边割。

根据最大流最小割定理:源S到汇T的网络最大流等于S与T间最小边割集的容量和。只需对新图求网络最大流,记为netflow,在这里我用了Dinic。这样就完成了第一问,结果为netflow。

对于第二问,要求出最小割集。对于每个点i(非c1,c2),把边(i1,i2)去掉,求最大流,记为nowflow,记当前找到的最小割集中元素的数量为cnt。如果netflow-cnt=nowflow+1,那么点i一定是最小割集中的割点,记录下来。否则将边(i1,i2)重新加上。直到cnt=netflow,当前找的集合就是最小割集。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3644 KB]
   Test 2: TEST OK [0.011 secs, 3640 KB]
   Test 3: TEST OK [0.011 secs, 3644 KB]
   Test 4: TEST OK [0.000 secs, 3644 KB]
   Test 5: TEST OK [0.000 secs, 3640 KB]
   Test 6: TEST OK [0.011 secs, 3640 KB]
   Test 7: TEST OK [0.000 secs, 3644 KB]
   Test 8: TEST OK [0.011 secs, 3640 KB]
   Test 9: TEST OK [0.032 secs, 3640 KB]
   Test 10: TEST OK [0.054 secs, 3644 KB]
   Test 11: TEST OK [0.097 secs, 3640 KB]

All tests OK.

Your program ('telecow') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!

第一次写Dinic,很冗长。

/*
ID: cmykrgb1
PROG: telecow
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAX 201
#define INF 0x7FFFFFFF

using namespace std;

class Tadjl
{
public:
	int cnt;
	int to[MAX];
	Tadjl(){cnt=0;}
	void ins(int k){to[++cnt]=k;}
};

class Tqueue
{
private:
	long first,last;
	long list[MAX*MAX];
public:
	long size;
	
	Tqueue()
	{
		reset();
	}
	
	void reset()
	{
		first=1;
		last=size=0;
	}
	
	void ins(long k)
	{
		size++;
		list[++last]=k;
	}
	
	long del()
	{
		size--;
		return list[first++];
	}
};

class Tstack
{
public:
	int stack[MAX];
	int top;
	int min,p;
	void reset()
	{
		top=0;
		min=INF;
	}

	Tstack()
	{
		reset();
	}
	void ins(int k)
	{
		stack[++top]=k;
	}
	void del()
	{
		top--;
	}
};

ifstream fi("telecow.in");
ofstream fo("telecow.out");
Tqueue Q;
Tstack AP;
int c1,c2,RN,RM,S,T,netflow;
Tadjl adjl[MAX];
int odis[MAX][MAX],dis[MAX][MAX],Flow[MAX][MAX];
int level[MAX],set[MAX];
bool used[MAX];

void init()
{
	int i,a,b,a1,a2,b1,b2,c;
	fi >> RN >> RM >> c1 >> c2;
	if (c1>c2) {c=c1;c1=c2;c2=c;}
	for (i=1;i<=RN;i++)
	{
		a=i*2-1;b=i*2;
		adjl[a].ins(b);
		dis[a][b]=1;
		adjl[b].ins(a);
		dis[b][a]=0;
	}
	for (i=1;i<=RM;i++)
	{
		fi >> a >> b;
		if (a>b) {c=a;a=b;b=c;}
		a1=a*2-1;a2=a1+1;
		b1=b*2-1;b2=b1+1;
		adjl[a2].ins(b1);
		dis[a2][b1]=INF;
		adjl[b1].ins(a2);
		dis[b1][a2]=0;
		adjl[b2].ins(a1);
		dis[b2][a1]=INF;
		adjl[a1].ins(b2);
		dis[a1][b2]=0;
	}
	S=c1*2;
	adjl[T=c2*2-1].cnt=0;
	memcpy(odis,dis,sizeof(dis));
}

void Dinic_level()
{
	int i,j,k;
	Q.reset();
	memset(used,0,sizeof(used));
	memset(level,0,sizeof(level));
	Q.ins(S);
	while (Q.size)
	{
		i=Q.del();
		used[i]=true;
		for (k=1;k<=adjl[i].cnt;k++)
		{
			j=adjl[i].to[k];
			if (!dis[i][j]) continue;
			if (used[j] || j==1) continue;
			level[j]=level[i]+1;
			Q.ins(j);
		}
	}
}

void Dinic_Argument()
{
	int i,u,v;
	AP.stack[0]=S;
	for (i=1;i<=AP.top;i++)
	{
		u=AP.stack[i-1];
		v=AP.stack[i];
		if (dis[u][v]<AP.min)
		{
			AP.min=dis[u][v];
			AP.p=u;
		}
	}
	for (i=AP.top;i>=1;i--)
	{
		u=AP.stack[i-1];
		v=AP.stack[i];
		Flow[u][v]+=AP.min;
		dis[u][v]-=AP.min;
		dis[v][u]+=AP.min;
	}
}

bool Dinic_dfs(int u)
{
	int outdegree=0;
	int i,v;
	bool B;
	if (u!=T)
	{
		for (i=1;i<=adjl[u].cnt;i++)
		{
			v=adjl[u].to[i];
			if (level[v]==level[u]+1 && dis[u][v])
			{
				outdegree++;
				AP.ins(v);
				B=Dinic_dfs(v);
				AP.del();
				if (B && u!=AP.p)
					return true;
			}
		}
		if (outdegree==0)
			level[u]=0;
	}
	else
	{
		Dinic_Argument();
		return true;
	}
	return false;
}

void Dinic()
{
	memset(Flow,0,sizeof(Flow));
	for (;;)
	{
		Dinic_level();
		if (level[T]==0)
			return;
		AP.reset();
		Dinic_dfs(S);
	}
}

int getflow()
{
	int i,flow=0;
	for (i=1;i<=RN*2;i++)
		flow+=Flow[S][i];
	return flow;
}

void Getset()
{
	int i,a,b,nowflow,cnt=0;
	Dinic();
	netflow=getflow();

	
	for (i=1;i<=RN;i++)
	{
		if (i!=c1 && i!=c2)
		{
			a=i*2-1;b=a+1;
			odis[a][b]=0;
			memcpy(dis,odis,sizeof(odis));
			Dinic();
			nowflow=getflow();
			if (nowflow+1==netflow-cnt)
				set[++cnt]=i;
			else
				odis[a][b]=1;
		}
		if (cnt==netflow)
			return;
	}
}

void print()
{
	int i;
	fo << netflow << endl << set[1];
	
	for (i=2;i<=netflow;i++)
		fo <<' ' << set[i];
	fo << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	Getset();
	print();
	return 0;
}

上次修改时间 2017-02-03

相关日志