[ZOJ3348 Schedule]网络流

【题目大意】
知道之前的比赛结果，和将要打的对阵。问DD有没有可能得冠军？（不能是并列冠军）
【算法分析】
很直观的想法，剩余的对阵里，如果有DD，那么让DD赢。
否则设为未群定比赛。
然后最后构一个二分图，把比赛分给那些人。
那些人还能剩多少场允许胜，那么就连这么多容量的边。
大概这样。
【其它】。。。之前WA成SB，重写1Y。泪流满面。
居然跑了个第一，照个相，不然马上被刷下来了。

【CODE】
#include #include #include #define clr(a) memset(a,0,sizeof(a))
const int maxn=55;
const int N=20005;
struct edge{int x,y,c;edge *next,*op;};
struct Network_t{
edge *ls[N],*cur[N],*fa[N];
int d[N],gap[N],Flow,S,T;
void init(int n){
for (int i=0;i<=n;i++)
while (ls[i]){
edge *t=ls[i];
ls[i]=t->next;
free(t);
}
}

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

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

void change(){
int NF=0x7FFFFFFF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c Flow+=NF;
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=NF;
fa[i]->op->c+=NF;
}
}

void sap(int n){
int i;
Flow=0;
for (i=0;i<=n;i++){
cur[i]=ls[i];
d[i]=0;
gap[i]=0;
}
gap[0]=n+1;
i=S;
while (d[S]<=n){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==T){
change();
i=S;
}
}else{
if (!–gap[d[i]]) return;
relabel(i,n);
gap[d[i]]++;
if (i!=S) i=fa[i]->x;
}
}
}
}Network;

int n,m,cnt,NL;
int win[maxn];
char Name[maxn][22];

int Get(char *str){
int i,j;
bool flag;
for (i=1;i<=n;i++){
flag=true;
for (j=0;j<22;j++)
if (str[j]!=Name[i][j]){
flag=false;
break;
}
if (flag) return i;
}
n++;
for (j=0;j<22;j++) Name[n][j]=str[j];
return n;
}

void init(){
clr(Name);
clr(win);
Network.init(N-1);
char s1[22],s2[22],s3[22];
n=1; Name[1][0]=Name[1][1]=’D’;
for (int x,y,i=1;i<=m;i++){
clr(s1); clr(s2); clr(s3);
scanf("%s%s%s",s1,s2,s3);
x=Get(s1);
y=Get(s2);
if (s3[0]==’w’) win[x]++;
else win[y]++;
}

Network.S=0; Network.T=1; cnt=0;
scanf("%d",&m);
for (int x,y,i=1;i<=m;i++){
clr(s1); clr(s2);
scanf("%s%s",s1,s2);
x=Get(s1);
y=Get(s2);
if (x==1) win[1]++;
if (y==1) win[1]++;
if (x!=1 && y!=1){
cnt++;
Network.addedge(x,NL+cnt,1);
Network.addedge(y,NL+cnt,1);
Network.addedge(NL+cnt,Network.T,1);
}
}
}

bool solve(){
for (int i=2;i<=n;i++)
if (win[i]>=win[1]) return false;
for (int i=2;i<=n;i++)
Network.addedge(Network.S,i,win[1]-win[i]-1);
Network.sap(NL+cnt);
if (Network.Flow==cnt) return true;
return false;
}

int main(){
clr(Network.ls);
while (scanf("%d%d",&NL,&m)!=EOF){
init();
if (solve()) puts("Yes");
else puts("No");
}
}