记录编号	61241	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 圆桌聚餐	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2013-06-06 18:05:00	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEN=500,INF=0x7fffffff;
int N;
int numu,numt;//单位数和桌子数
int allr;
int S,T;
class EDGE{
public:
	int from,to,cap,flow;
};
vector<EDGE> edges;
vector<int> c[SIZEN];//邻接表
queue<int> Q;//溢出节点
int h[SIZEN]={0},e[SIZEN]={0};
int finalflow=0;
void addedge(int from,int to,int cap){
	edges.push_back((EDGE){from,to,cap,0});
	edges.push_back((EDGE){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
void push(int x,int k){//x通过edges的第k条边压
	EDGE& now=edges[k];
	if(now.cap<=now.flow) return;
	int cf=min(now.cap-now.flow,e[x]);
	now.flow+=cf,edges[k^1].flow-=cf;
	e[now.to]+=cf,e[x]-=cf;
	if(now.to!=T&&now.to!=S&&e[now.to]) Q.push(now.to);
}
void singlenode(int x){
	int i,nowmin;
	#define now edges[c[x][i]]
	while(e[x]){
		nowmin=INF;
		for(i=0;i<c[x].size();i++){
			if(now.cap>now.flow){
				if(h[now.to]==h[x]-1){
					push(x,c[x][i]);
					if(!e[x]) return;
				}
				else nowmin=min(nowmin,h[now.to]);
			}
		}
		h[x]=nowmin+1;
	}
}
void maxflow(void){//push & relable
	int i,x;
	h[S]=N,e[S]=INF;
	for(i=0;i<c[S].size();i++) push(S,c[S][i]);
	while(!Q.empty()){
		x=Q.front();Q.pop();
		singlenode(x);
	}
	finalflow=0;
	for(i=0;i<c[S].size();i++) finalflow+=edges[c[S][i]].flow;
}
int rep[SIZEN]={0},table[SIZEN]={0};//代表数和餐桌容量
void init(void){
	scanf("%d%d",&numu,&numt);
	N=numu+numt+1;//0~N,其中0是源,N是汇
	S=0,T=N;
	allr=0;
	int i,j;
	for(i=1;i<=numu;i++) scanf("%d",&rep[i]),allr+=rep[i];
	for(i=1;i<=numt;i++) scanf("%d",&table[i]);
	for(i=numu;i>=1;i--) addedge(S,i,rep[i]);
	for(i=numt;i>=1;i--) addedge(numu+i,T,table[i]);
	for(i=numu;i>=1;i--){
		for(j=numt;j>=1;j--) addedge(i,numu+j,1);
	}
}
void write(void){
	if(finalflow<allr){
		printf("0\n");
		return;
	}
	printf("1\n");
	int i,j;
	for(i=1;i<=numu;i++){
		for(j=0;j<c[i].size();j++){
			if(edges[c[i][j]].to!=S&&edges[c[i][j]].flow){
				printf("%d ",edges[c[i][j]].to-numu);
			}
		}
		printf("\n");
	}
}
int main(){
	freopen("roundtable.in","r",stdin);
	freopen("roundtable.out","w",stdout);
	init();
	maxflow();
	write();
	return 0;
}