HDU 3605 Escape最大ストリームor二分図多重整合2010 ACM-ICPC Multi-University Training Contest(17)——Host by ZSTU

Escape
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1122 Accepted Submission(s): 321
Problem Description
2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but some people do not fit to live some of the planet. Now scientists want your help, is to determine what all of people can live in these planets.
Input
More set of test data, the beginning of each data is n (1 <= n <= 100000), m (1 <= m <= 10) n indicate there n people on the earth, m representatives m planet, planet and people labels are from 0. Here are n lines, each line represents a suitable living conditions of people, each row has m digits, the ith digits is 1, said that a person is fit to live in the ith-planet, or is 0 for this person is not suitable for living in the ith planet.
The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most..
0 <= ai <= 100000
Output
Determine whether all people can live up to these stars
If you can output YES, otherwise output NO.
Sample Input
1 1 1 1
2 2 1 0 1 0 1 1
Sample Output
YES
NO
Source
2010 ACM-ICPC Multi-University Training Contest(17)——Host by ZSTU
Recommend
lcy
 
 
一見するとネットワークストリームで、テンプレートを構築して提出し、RE...
計算を小さくしてTLEに変えて、それからいろいろな方法を尽くしてやはりTLEです
ネットストリームではないのではないかと疑い始めました.ポイントが多すぎるからです.
二分図多重マッチングに変えてTLE...
杯具の人は今晩0 ACになると思っていました...
そこで思わず解題報告書を探してみましたが、
確かにネットワークフロー解法はありますが、n=10^6はTLEを肯定しますが、m<=10は小さいので、
全員の選択は2^m種しかなく、この2^mで選択した数を統計すると、
この2^m種はノードとしてm個の星ノードに接続する辺権を統計的な数として選択し、
ソースポイントsはこれらのノードの辺権同上(私が書いたinfはずっとWAで、どうして間違っているのか)、
m個の星ノードは合流点tに辺を接続し、辺権は星容量である.
これで10^6のノードを10^3に減らすとTLEがなくなります.
実は午后、データの范囲を缩小するような问题をしたばかりなのに、どうして夜に忘れてしまったのですか.の
ACMDIY第2回グループリーグ
Ahui Writes Word
:01リュックの問題ですが、n=10000000、v=10000000
TLEは肯定的ですが、体積も価値も「=10で、100種類のアイテムに変換できる多重リュックサックです.
さらにバイナリ圧縮で01リュックに変換して解く.
-------------------------------------------------------------------------------------------------------
本題はまた2分図の多重整合解を使うことができて、ちょうどマークの配列を大きくして、ずっとTLEを招きます...
マーク配列は10をつけるだけで十分で、私は10万を作って、タイムアウトしないのがおかしいです..
 
あとこれはC++で提出しなければタイムアウトしませんが、入力外挂G++、C++でもとても速いです.
 
最大ストリームコード:

#include<cstdio>
#include<cstring>
#define N 2005
#define M 30005
#define inf 999999999
#define min(a,b) ((a)<(b)?(a):(b))

int n,m,s,t,num,adj[N],dis[N],q[N];
struct edge
{
	int v,w,pre;
	edge(){}
	edge(int vv,int ww,int p){v=vv;w=ww;pre=p;}
}e[M];
void insert(int u,int v,int w)
{
	e[num]=edge(v,w,adj[u]);
	adj[u]=num++;
	e[num]=edge(u,0,adj[v]);
	adj[v]=num++;
}
int bfs()
{
	int i,x,v,head=0,tail=0;
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	q[++tail]=s;
	while(head!=tail)
	{
		x=q[head=(head+1)%N];
		for(i=adj[x];~i;i=e[i].pre)
			if(e[i].w&&!dis[v=e[i].v])
			{
				dis[v]=dis[x]+1;
				if(v==t)
					return 1;
				q[tail=(tail+1)%N]=v;
			}
	}
	return 0;
}
int dfs(int x,int limit)
{
	if(x==t)
		return limit;
	int i,v,tmp,cost=0;
	for(i=adj[x];~i&&cost<limit;i=e[i].pre)
		if(e[i].w&&dis[x]==dis[v=e[i].v]-1)
		{
			tmp=dfs(v,min(limit-cost,e[i].w));
			if(tmp)
			{
				e[i].w-=tmp;
				e[i^1].w+=tmp;
				cost+=tmp;
			}
			else
				dis[v]=-1;
		}
	return cost;
}
int Dinic()
{
	int ans=0;
	while(bfs())
		ans+=dfs(s,inf);
	return ans;
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		int i,j,k,a,w,x[2005]={0};
		memset(adj,-1,sizeof(adj));
		num=0;
		s=0;
		t=2000;
		for(i=0;i<n;i++)
		{
			k=0;
			for(j=0;j<m;j++)
			{
				scanf("%d",&a);
				if(a)
					k|=1<<j;
			}
			x[k]++;
		}
		for(i=0;i<(1<<m);i++)
			if(x[i])
			{
				insert(s,i+1,x[i]);
				for(j=0;j<m;j++)
					if(i&(1<<j))
						insert(i+1,j+10+(1<<m),x[i]);
			}
		for(j=0;j<m;j++)
		{
			scanf("%d",&w);
			insert(j+10+(1<<m),t,w);
		}
		puts(Dinic()>=n?"YES":"NO");
	}
}

二分図多重整合コード:

#include<cstdio>
#include<cstring>
#include<iostream>

int n,m,w[15],cnt[15];
int adj[100010][12],mat[12][100010];
bool f[15];
bool dfs(int x)
{
	int i,j,v;
	for(i=0;i<m;i++)
		if(!f[i]&&adj[x][i])
		{
			f[i]=1;
			if(cnt[i]<w[i])
			{
				mat[i][cnt[i]++]=x;
				return true;
			}
			for(j=0;j<cnt[i];j++)
				if(dfs(mat[i][j]))
				{
					mat[i][j]=x;
					return true;
				}
		}
	return false;
}
bool ok()
{	
	int i;
	memset(cnt,0,sizeof(cnt));
	for(i=0;i<n;i++)
	{
		memset(f,0,sizeof(f));
		if(!dfs(i))
			return false;
	}
	return true;
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		int i,j;
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				scanf("%d",&adj[i][j]);
		for(j=0;j<m;j++)
			scanf("%d",&w[j]);
		puts(ok()?"YES":"NO");
	}
}