OJ Board

Code: Select all

#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

#define FOR(i,a,b)   for(int i=(a);i<(b);i++)
#define REP(i,a,b)   for(int i=(a);i<=(b);i++)
#define PB           push_back

#define sz 1040

int N,M;
int cap[sz][sz],flow[sz][sz],parent[sz],s,t;
int vd[25][sz];
int top[25];

void init_p()
{
	int lim = N+M+5;
	FOR(i,0,lim)parent[i]=-1;
}

//MAX-FLOW: FORD FULKERSON..RESIDUAL GRAPH
bool path()
{
	int u;
	queue<int> qu;
	char color[sz];
	init_p();
	memset(color,0,sizeof(color));
	color[s] = 1;
	qu.push(s);
	while(qu.empty()==false)
	{
		u = qu.front();
		if(u==t)break;
		qu.pop();
		REP(i,0,t)
		{
			if(((cap[u][i]-flow[u][i]) > 0) && color[i]==0)
			{
				color[i] = 1;
				parent[i] = u;
				qu.push(i);
				if(i==t)break;
			}
		}
	}
	if(color[t]==0)return false;
	int now,previous;
	now = t;
	while(parent[now] != -1)
	{
		previous = parent[now];
		flow[previous][now] += 1;
		flow[now][previous] = -flow[previous][now];
		now = previous;
	}
	now = t;
	int ind,ins;
	while(1)
	{
		if(parent[parent[now]]==s)
		{
			ind = parent[now];
			ins = now;
			break;
		}
		now = parent[now];
	}
	vd[ind][top[ind]++] = ins;
	return true;
}

void init()
{
	int lim = N+M+5;
	FOR(i,0,lim)
	{
		FOR(j,0,lim)
		{
			cap[i][j] = flow[i][j] = 0;
		}
	}
	REP(i,0,N)
	{
		top[i] = 0;
		REP(j,0,lim)
		{
			vd[i][j] = 0;
		}
	}
}

int main()
{
//	  freopen("10092.in","r",stdin);
	int capacity,l,val;
	while(1)
	{
		scanf("%d %d",&N,&M);
		if(N==0 && M==0)break;
		s = capacity = 0;
		init();
		REP(i,1,N)
		{
			scanf("%d",&cap[s][i]);
			cap[i][s] = cap[s][i];
			capacity += cap[s][i];
		}
		t = N+M+1;
		FOR(i,N+1,t)
		{
			scanf("%d",&l);
			FOR(j,0,l)
			{
				scanf("%d",&val);
				cap[val][i] = 1;
			}
		}
		FOR(i,N+1,t)
		{
			cap[i][t] = 1;
		}
		int cnt = 0;
		while(path()==true)
		{
			cnt++;
		}
		if(cnt<capacity)
		{
			printf("0\n");
			continue;
		}
		printf("1\n");
		int li;
		REP(i,1,N)
		{
			li = top[i];
			FOR(j,0,li)
			{
				if(j>0)printf(" %d",vd[i][j]-N);
				else printf("%d",vd[i][j]-N);
			}
			printf("\n");
		}
	}
	return 0;
}

Code: Select all

2 2
1 1
2 1 2
1 1

Code: Select all

#include <cstdio>
#include <queue>

using namespace std;

#define FOR(i,a,b)   for(int i=(a);i<(b);i++)
#define REP(i,a,b)   for(int i=(a);i<=(b);i++)

#define sz 1040

int N,M,cnt;
int cap[sz][sz],flow[sz][sz],parent[sz],s,t;
int vd[25][sz];
int top[25],pt[25];

void init_p()
{
	int lim = N+M+5;
	FOR(i,0,lim)parent[i]=-1;
}

//MAX-FLOW: FORD FULKERSON..RESIDUAL GRAPH
bool path()
{
	int u;
	queue<int> qu;
	char color[sz];
	init_p();
	memset(color,0,sizeof(color));
	color[s] = 1;
	qu.push(s);
	while(qu.empty()==false)
	{
		u = qu.front();
		qu.pop();
		REP(i,1,t)
		{
			if((cap[u][i]-flow[u][i])>0 && color[i]==0)
			{
				color[i] = 1;
				parent[i] = u;
				qu.push(i);
				if(i==t)break;
			}
		}
		if(color[t]==1)break;
	}
	if(color[t]==0)return false;
	int now,previous;
	now =t;
	while(parent[now] != -1)
	{
		previous = parent[now];
		if(previous>0 && previous<=N && now>N && now<t)
		{
			vd[previous][top[previous]++] = now;
		}
		flow[previous][now] += 1;
		flow[now][previous] = -flow[previous][now];
		now = previous;
	}
	return true;
}

void init()
{
	int lim = N+M+5;
	FOR(i,0,lim)
	{
		FOR(j,0,lim)
		{
			cap[i][j] = flow[i][j] = 0;
		}
	}
	REP(i,0,N+2)
	{
		top[i] = 0;
	}
}

int main()
{
//	  freopen("10092.in","r",stdin);
	int capacity,l,val;
	while(1)
	{
		scanf("%d %d",&N,&M);
		if(N==0 && M==0)break;
		s = capacity = 0;
		init();
		REP(i,1,N)
		{
			scanf("%d",&cap[s][i]);
			pt[i] = cap[s][i];
			capacity += cap[s][i];
		}
		t = N+M+1;
		FOR(i,N+1,t)
		{
			scanf("%d",&l);
			FOR(j,0,l)
			{
				scanf("%d",&val);
				cap[val][i] = 1;
			}
		}
		FOR(i,N+1,t)
		{
			cap[i][t] = 1;
		}
		cnt = 0;
		while(path()==true)
		{
			cnt++;
		}
		if(cnt<capacity)
		{
			printf("0\n");
			continue;
		}
		printf("1\n");
		int li,prob;
		REP(i,1,N)
		{
			li = top[i];
			prob = pt[i];
			FOR(j,0,prob)
			{
				if(j>0)printf(" %d",vd[i][li-pt[i]]-N);
				else printf("%d",vd[i][li-pt[i]]-N);
				pt[i]--;
			}
			printf("\n");
		}
	}
	return 0;
}