TIOJ 1236 工廠生產問題 [ TOI 2006 ] [Flow]

poao899    184K    289MS    G++     1.62K     2009-12-10 16:13:52                                   .

一樣是Flow =w=


唔MAX一開始調10^9會WA

哪家工廠生產這麼有效率啦（翻桌


是說這題要拆點、沒給測資範圍

然後就沒什麼特別了(?


//****************************

#include<stdio.h>
#define QLEN 1000100
#define MAX 2147483647
#define NMAX 1000
struct arc{
	int j,con;
	arc *next,*topair;
	void set(int to,int c,arc* n,arc* t){
		j=to;con=c;
		next=n;topair=t;
	}
}A[1000000],*N[NMAX],*from[NMAX];
int que[QLEN];
struct queue{
	int front,rear;
	int *ar;
	void init(){
		ar=que;
		front=rear=0;
	}
	void enq(int a){
		ar[rear]=a;
		rear=++rear%QLEN;
	}
	int deq(){
		int x=ar[front];
		front=++front%QLEN;
		return x;
	}
}q;
arc* get(){
	static int cnt=0;
	return A+cnt++;
}
void build(int i,int j,int con){
	arc *p=get(),*q=get(),*r;
	r=N[i];
	N[i]=p;
	p->set(j,con,r,q);
	r=N[j];
	N[j]=q;
	q->set(i,0,r,p);
}
int n,m,a,b,f,max,indeg[NMAX],outdeg[NMAX],fa[NMAX],c;
int bfs(){
	for(int i=0;i<NMAX;i++)
		fa[i]=-1;
	q.init();
	q.enq(0);
	int flow=MAX;
	while(q.front!=q.rear){
		int now=q.deq();
		for(arc *p=N[now];p;p=p->next){
			if(fa[p->j]==-1 && p->con > 0){
				q.enq(p->j);
				fa[p->j]=now;
				from[p->j]=p;
				if(flow > p->con)
					flow=p->con;
			}
		}
	}
	if(fa[999]==-1)return 0;
	return flow;
}
void resi(int flow){
	for(int now=999;now;now=fa[now]){
		from[now]->con-=flow;
		from[now]->topair->con+=flow;
	}
}
main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&c);
		build(i,i+500,c);
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		build(a+500,b,MAX);
		indeg[b]++;
		outdeg[a]++;
	}
	for(int i=1;i<=n;i++){
		if(!indeg[i])
			build(0,i,MAX);
		if(!outdeg[i])
			build(i+500,999,MAX);
	}
	while(1){
		f=bfs();
		if(!f)break;
		resi(f);
		max+=f;
	}
	printf("%d\n",max);
}