[SGU 326]网络流

【题目大意】有N只球队，给出他们已经赢了的场数和剩下比赛的场数(包括跨赛区和本赛区的)，再给定本赛区剩下比赛的对战情况。求球队1能否得到冠军？（即球队1赢球场数位列第1，可以并列）

【算法分析】对于跨赛区的，就当他1的全赢了，其它队的全输了。对于本赛区的，与1有关的比赛肯定都当1赢了，然后就需要分配剩下的比赛给哪个队赢，使得其它球队赢球场数都<=球队1赢的场数。从这个分配上我们很容易想到网络流。
建立一个二分图，左边是比赛，右边是队伍。然后连边就脑残了。

【其它】第一次用C++的指针，居然1A，HAPPY
993680 31.01.10 18:11 edward 326 .CPP Accepted 25 ms 31 kb
【CODE】
#include #include #define N 1000
#define inf 0x7FFFFFFF
struct edge{int x,y,c;edge *op,*next;};
int d[N],num[N],w[21],r[21],a[21][21];
edge *ls[N],*cur[N],*fa[N];
int n,e,T;

void init(){
for (int i=0;iscanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&w[i]); 
for (int i=1;i<=n;i++) scanf("%d",&r[i]);   
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}  

void relabel(int k){
int mm=T;
cur[k]=ls[k];
for (edge *t=ls[k];t;t=t->next)
if (t->c && d[t->y]d[k]=mm+1;
}   

void change(){
int nf=inf;
for (int i=T;i!=0;i=fa[i]->x)
if (fa[i]->cfor (int i=T;i!=0;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}   
}   

void sap(){
for (int i=0;i<=T;i++) cur[i]=ls[i];
int i=0;
while (d[0]for (;cur[i];cur[i]=cur[i]->next)
if (cur[i]->c && d[cur[i]->y]+1==d[i]) break;
if (!cur[i]){
if (!–num[d[i]]) break;
relabel(i);
num[d[i]]++;
if (i!=0) i=fa[i]->x;
}   
else{
fa[cur[i]->y]=cur[i];
i=cur[i]->y;
if (i==T){
change();
i=0;
}   
}   
}   
}   

void addedge(int x,int y,int c){
edge *p=new edge; edge *q=new edge;
p->x=x; p->y=y; p->c=c; p->op=q; p->next=ls[x]; ls[x]=p;
q->x=y; q->y=x; q->c=0; q->op=p; q->next=ls[y]; ls[y]=q;
}   

bool work(){
w[1]+=r[1];
for (int i=2;i<=n;i++)
if (w[i]>w[1]) return false;
T=n;
for (int i=2;i<=n;i++)
for (int j=i+1;j<=n;j++)
if (a[i][j]){
T++;
addedge(0,T,a[i][j]);
addedge(T,i,inf);
addedge(T,j,inf);
}   
T++;
for (int i=2;i<=n;i++) addedge(i,T,w[1]-w[i]);
sap();
for (edge *t=ls[0];t;t=t->next)
if (t->c>0) return false;
return true;
}   

int main(){
init();
if (work()) printf("YESn");
else printf("NOn");
}