Boleyn Su's Blog – 第 9 页

POJ3308[Paratroopers]

最小割，第一次做容量是实数的网络流，WA了N次，一直以为是浮点误差没处理好。

后来才发现是printf(“%lf”,xxx)出了问题，printf有时候不认%lf，但是一定认%f。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-21

DESCRIPTION:

网络流 乱做

http://acm.pku.edu.cn/JudgeOnline/problem?id=3308

#include <stdio.h>

#include <string.h>

#include <math.h>

const double oo=1e10;

const double zero=1e-10;

const int MAXV=1000000;

const int MAXE=1000000;

typedef struct struct_edge* edge;

struct struct_edge{int v;double c;edge n,b;};

struct_edge pool[MAXE];

edge top;

int S,T,V;

edge adj[MAXV];

int d[MAXV];

int q[MAXV];

int head,tail;

void add_edge(int u,int v,double c)

{

top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

adj[u]->b=adj[v],adj[v]->b=adj[u];

}

bool is_zero(double a)

{

return fabs(a)<=zero;

}

bool relabel()

{

for (int i=0;i<V;d[i++]=V) ;

d[q[head=tail=0]=T]=0;

while (head<=tail)

{

int u=q[head++];

for (edge i=adj[u];i;i=i->n)

if (!is_zero(i->b->c)&&d[i->v]==V)

d[q[++tail]=i->v]=d[u]+1;

if (d[S]!=V) return true;

}

return false;

}

double augment(int u,double e)

{

if (u==T) return e;

double f=0;

for (edge i=adj[u];i&&!is_zero(e);i=i->n)

if (!is_zero(i->c)&&d[u]==d[i->v]+1)

{

double df=augment(i->v,e<i->c?e:i->c);

i->c-=df,i->b->c+=df,e-=df,f+=df;

}

return f;

}

double dinic()

{

double f=0;

while (relabel()) f+=augment(S,oo);

return f;

}

int t;

int m,n,l;

int main()

{

scanf(“%d”,&t);

for (int tt=0;tt<t;tt++)

{

scanf(“%d%d%d”,&m,&n,&l);

top=pool;

memset(adj,0,sizeof(adj));

S=0,T=m+n+1,V=m+n+2;

for (int i=1;i<=m;i++)

{

double a;

scanf(“%lf”,&a);

add_edge(S,i,log(a));

}

for (int i=1;i<=n;i++)

{

double a;

scanf(“%lf”,&a);

add_edge(i+m,T,log(a));

}

for (int i=0;i<l;i++)

{

int a,b;

scanf(“%d%d”,&a,&b);

add_edge(a,b+m,oo);

}

printf(“%.4f\n”,double(exp(dinic())));

}

SPOJ839[Optimal Marks]

最小割。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-20

DESCRIPTION:

网络流 乱做

http://www.spoj.pl/problems/OPTM/

#include <stdio.h>

#include <string.h>

const int oo=(~0u)>>1;

const int MAXV=1000000;

const int MAXE=1000000;

typedef struct struct_edge* edge;

struct struct_edge{int v,c;edge n,b;};

struct_edge pool[MAXE];

edge top;

int S,T,V;

edge adj[MAXV];

int d[MAXV];

int q[MAXV];

int head,tail;

void add_edge(int u,int v,int c)

{

top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

adj[u]->b=adj[v],adj[v]->b=adj[u];

}

bool relabel()

{

for (int i=0;i<V;d[i++]=oo) ;

d[q[head=tail=0]=T]=0;

while (head<=tail)

{

int u=q[head++];

for (edge i=adj[u];i;i=i->n)

if (i->b->c&&d[i->v]==oo)

d[q[++tail]=i->v]=d[u]+1;

if (d[S]!=oo) return true;

}

return false;

}

int augment(int u,int e)

{

if (u==T) return e;

int f=0;

for (edge i=adj[u];i&&e;i=i->n)

if (i->c&&d[u]==d[i->v]+1)

if (int df=augment(i->v,e<i->c?e:i->c))

i->c-=df,i->b->c+=df,e-=df,f+=df;

return f;

}

int dinic()

{

int f=0;

while (relabel()) f+=augment(S,oo);

return f;

}

const int SIZE=1000000;

int t;

int n,m,k;

int a[SIZE],b[SIZE],u[SIZE],p[SIZE],o[SIZE],visited[SIZE];

void dfs(int u,int length)

{

visited[u]=true;

o[u]|=1<<length;

for (edge i=adj[u];i;i=i->n)

if (i->c&&!visited[i->v]) dfs(i->v,length);

}

int main()

{

scanf(“%d”,&t);

for (int tt=0;tt<t;tt++)

{

scanf(“%d%d”,&n,&m);

for (int i=0;i<m;i++)

scanf(“%d%d”,a+i,b+i);

scanf(“%d”,&k);

for (int i=0;i<k;i++)

scanf(“%d%d”,u+i,p+i);

for (int i=1;i<=n;o[i++]=0) ;

for (unsigned int bit=1,length=0;bit;bit<<=1,length++)

{

top=pool;

for (int i=0;i<V;i++) visited[i]=int(adj[i]=0);

S=0,T=n+1,V=n+2;

for (int i=0;i<k;i++)

if (p[i]&bit) add_edge(S,u[i],oo);

else add_edge(u[i],T,oo);

for (int i=0;i<m;i++)

add_edge(a[i],b[i],1),add_edge(b[i],a[i],1);

dinic();

dfs(S,length);

}

for (int i=1;i<=n;i++) printf(“%d\n”,o[i]);

}

HNU10940[Coconuts]

有一个源S，连支持的人。
有一个汇T，连反对的人。
朋友间相互连边。
形成一个图。
现在问最少去多少边可以使S与T不连通。
与S连通的表示他们支持。
与T连通的表示他们反对。
可以用最小割做。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-20

DESCRIPTION:

网络流 乱做

http://acm.hnu.cn/online/?action=problem&type=show&id=10940

#include <stdio.h>

#include <string.h>

const int oo=(~0u)>>1;

const int MAXV=1000000;

const int MAXE=1000000;

typedef struct struct_edge* edge;

struct struct_edge{int v,c;edge n,b;};

struct_edge pool[MAXE];

edge top;

int S,T,V;

edge adj[MAXV];

int d[MAXV];

int q[MAXV];

int head,tail;

void add_edge(int u,int v,int c)

{

top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

adj[u]->b=adj[v],adj[v]->b=adj[u];

}

bool relabel()

{

for (int i=0;i<V;d[i++]=oo) ;

d[q[head=tail=0]=T]=0;

while (head<=tail)

{

int u=q[head++];

for (edge i=adj[u];i;i=i->n)

if (i->b->c&&d[i->v]==oo)

d[q[++tail]=i->v]=d[u]+1;

if (d[S]!=oo) return true;

}

return false;

}

int augment(int u,int e)

{

if (u==T) return e;

int f=0;

for (edge i=adj[u];i&&e;i=i->n)

if (i->c&&d[u]==d[i->v]+1)

if (int df=augment(i->v,e<i->c?e:i->c))

i->c-=df,i->b->c+=df,e-=df,f+=df;

return f;

}

int dinic()

{

int f=0;

while (relabel()) f+=augment(S,oo);

return f;

}

int n,m,a,b;

int main()

{

for (;;)

{

scanf(“%d%d”,&n,&m);

if (!n&&!m) break;

top=pool;

memset(adj,0,sizeof(adj));

S=0,T=n+1,V=n+2;

for (int i=1;i<=n;i++)

scanf(“%d”,&a),a?add_edge(S,i,1):add_edge(i,T,1);

for (int i=0;i<m;i++)

scanf(“%d%d”,&a,&b),add_edge(a,b,1),add_edge(b,a,1);

printf(“%d\n”,dinic());

}

ZOJ2532[Internship]

网络流。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-20

DESCRIPTION:

网络流 乱做

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1532

#include <stdio.h>

#include <string.h>

const int oo=(~0u)>>1;

const int MAXV=1000000;

const int MAXE=1000000;

typedef struct struct_edge* edge;

struct struct_edge{int v,c;edge n,b;};

struct_edge pool[MAXE];

edge top;

int S,T,V;

edge adj[MAXV];

int d[MAXV];

int q[MAXV];

int head,tail;

void add_edge(int u,int v,int c)

{

top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

adj[u]->b=adj[v],adj[v]->b=adj[u];

}

bool relabel()

{

for (int i=0;i<V;d[i++]=oo) ;

d[q[head=tail=0]=T]=0;

while (head<=tail)

{

int u=q[head++];

for (edge i=adj[u];i;i=i->n)

if (i->b->c&&d[i->v]==oo)

d[q[++tail]=i->v]=d[u]+1;

if (d[S]!=oo) return true;

}

return false;

}

int augment(int u,int e)

{

if (u==T) return e;

int f=0;

for (edge i=adj[u];i&&e;i=i->n)

if (i->c&&d[u]==d[i->v]+1)

if (int df=augment(i->v,e<i->c?e:i->c))

i->c-=df,i->b->c+=df,e-=df,f+=df;

return f;

}

int dinic()

{

int f=0;

while (relabel()) f+=augment(S,oo);

return f;

}

const int MAXL=1000;

int n,m,l;

int a[MAXL],b[MAXL],c[MAXL];

int main()

{

for (;;)

{

scanf(“%d%d%d”,&n,&m,&l);

if (!n) break;

top=pool;

S=n+m+1,T=0,V=n+m+2;

for (int i=0;i<V;adj[i++]=0) ;

for (int i=0;i<l;i++)

scanf(“%d%d%d”,a+i,b+i,c+i),

add_edge(a[i],b[i],c[i]);

for (int i=1;i<=n;i++)

add_edge(S,i,oo);

int flow=dinic();

bool first=true;

for (int i=0;i<l;i++)

{

add_edge(a[i],b[i],oo);

if (relabel()) if (first) printf(“%d”,i+1),first=false;

else printf(” %d”,i+1);

adj[a[i]]=adj[a[i]]->n;top–;

adj[b[i]]=adj[b[i]]->n;top–;

}

printf(“\n”);

}

HDU3157[Crazy Circuits]

有下界的最小流。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-20

DESCRIPTION:

网络流 乱做

http://acm.hdu.edu.cn/showproblem.php?pid=3157

#include <stdio.h>

#include <string.h>

const int oo=(~0u)>>1;

const int MAXV=1102;

const int MAXE=6200;

typedef struct struct_edge* edge;

struct struct_edge{int v,c;edge n,b;};

struct_edge pool[MAXE];

edge top;

int S,T,V;

edge adj[MAXV];

int d[MAXV];

int q[MAXV];

int head,tail;

void add_edge(int u,int v,int c)

{

top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

adj[u]->b=adj[v],adj[v]->b=adj[u];

}

bool relabel()

{

for (int i=0;i<V;d[i++]=oo) ;

d[q[head=tail=0]=T]=0;

while (head<=tail)

{

int u=q[head++];

for (edge i=adj[u];i;i=i->n)

if (i->b->c&&d[i->v]==oo)

d[q[++tail]=i->v]=d[u]+1;

if (d[S]!=oo) return true;

}

return false;

}

int augment(int u,int e)

{

if (u==T) return e;

int f=0;

for (edge i=adj[u];i&&e;i=i->n)

if (i->c&&d[u]==d[i->v]+1)

if (int df=augment(i->v,e<i->c?e:i->c))

i->c-=df,i->b->c+=df,e-=df,f+=df;

return f;

}

int dinic()

{

int f=0;

while (relabel()) f+=augment(S,oo);

return f;

}

int N,M;

int ss,tt;

int total;

edge tt_to_ss;

bool read()

{

total=0;

top=pool;

memset(adj,0,sizeof(adj));

scanf(“%d%d”,&N,&M);

if (N==0&&M==0) return false;

ss=0,tt=N+1;

S=N+2,T=N+3,V=N+4;

for (int i=0;i<M;i++)

{

static const int MAXLENGTH=1024;

char s[MAXLENGTH];

int a,b,c;

scanf(“%s”,&s);

if (sscanf(s,“%d”,&a)==EOF)

if (*s==’+’) a=ss;

else if (*s==’-‘) a=tt;

scanf(“%s”,&s);

if (sscanf(s,“%d”,&b)==EOF)

if (*s==’+’) b=ss;

else if (*s==’-‘) b=tt;

scanf(“%d”,&c);

add_edge(a,b,oo);

add_edge(S,b,c);

add_edge(a,T,c);

total+=c;

}

add_edge(tt,ss,oo);

tt_to_ss=top-2;

return true;

}

void write()

{

total-=dinic();

if (total) printf(“impossible\n”);

else

{

S=N+1,T=0,V-=2;

int answer=tt_to_ss->b->c-dinic();

printf(“%d\n”,answer);

}

int main()

{

while (read()) write();

}

POJ3155[Hard Life]

最大密度子图，推荐读一下2007年国家集训队论文(胡伯涛《最小割模型在信息学竞赛中的应用》)。

恩，还有因为做NOI2006的最大获利/profit，我不得不学了ISAP和Dinic，因为Relabel-to-front过不了！而且HLPP也过不了！所以这里就用ISAP了。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-19

DESCRIPTION:

网络流 乱做

http://acm.pku.edu.cn/JudgeOnline/problem?id=3155

#include <stdio.h>

#include <string.h>

const int oo=(~0u)>>1;

const int MAXV=1102;

const int MAXE=6200;

typedef struct struct_edge* edge;

struct struct_edge{int v,c;edge n,b;};

struct_edge pool[MAXE];

edge top=pool;

int S,T,V;

edge adj[MAXV];

int d[MAXV],dn[MAXV+1];

void add_edge(int u,int v,int c)

{

top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

adj[u]->b=adj[v],adj[v]->b=adj[u];

}

int augment(int u,int e)

{

if (u==T) return e;

if (d[S]==V) return 0;

int f=0,mind=V-1;

for (edge i=adj[u];i;i=i->n)

if (i->c)

{

if (d[u]==d[i->v]+1)

{

int df=augment(i->v,e<i->c?e:i->c);

i->c-=df;

i->b->c+=df;

e-=df;

f+=df;

if (e==0) return f;

}

if (mind>d[i->v]) mind=d[i->v];

}

if (f) return f;

else

{

if (!–dn[d[u]]) d[S]=V;

else dn[d[u]=mind+1]++;

return 0;

}

int sap()

{

int f=0;

dn[0]=V;

while (d[S]<V) f+=augment(S,oo);

return f;

}

const int MAXN=100,MAXM=1000;

const int XX=MAXN*MAXN*MAXN;

int n,m;

int a[MAXM],b[MAXM];

bool visited[MAXN+MAXM+2];

int total;

void build_network(int rate)

{

memset(adj,0,sizeof(adj));

memset(d,0,sizeof(d));

memset(dn,0,sizeof(dn));

top=pool;

S=n+m,T=m+n+1,V=n+m+2;

for (int i=0;i<n;i++)

add_edge(S,i,rate);

for (int i=0;i<m;i++)

add_edge(a[i]-1,n+i,oo),

add_edge(b[i]-1,n+i,oo),

add_edge(n+i,T,XX);

}

void dfs(int u)

{

visited[u]=true;

for (edge i=adj[u];i;i=i->n)

if (!visited[i->v]&&i->c)

dfs(i->v);

}

void read()

{

scanf(“%d%d”,&n,&m);

for (int i=0;i<m;i++)

scanf(“%d%d”,a+i,b+i);

}

void write()

{

if (!m)

{

printf(“%d\n%d\n”,1,1);

return;

}

int L=0*XX,R=m*XX,best;

{

int mid=(L+R)>>1;

build_network(mid);

int g=m*XX-sap();

if (g<=0) R=mid;

else L=mid,best=L;

}

while (L+1!=R);

build_network(best);

sap();

dfs(S);

for (int i=0;i<n;i++)

if (!visited[i]) total++;

printf(“%d\n”,total);

for (int i=0;i<n;i++)

if (!visited[i])

printf(“%d\n”,i+1);

}

int main()

{

read();

write();

}

线性规划与网络流24题[信息学资源]

[线性规划与网络流24题.zip]下载（貌似Google Documents已被墙，会翻墙的自己翻墙下，不会的在下面留个邮箱。）

由于有些题目需要special judge，所以我写了几个checker（checker是给Cena用的，要求程序名为prog8xx.yy，输入为prog8xx.in，输出为prog8xx.out，xx为题目编号，yy为源文件扩展名），有些题目已经有了现成的checker，所以我附上了可以提交的地方的链接。

里面还有我的程序（用C++写的，其中8,22,23没有做）。

博弈论之NIM取石子游戏与SG函数[信息学资料]

[博弈论之NIM取石子游戏与SG函数.zip]下载（貌似Google Documents已被墙，会翻墙的自己翻墙下，不会的在下面留个邮箱。）

前言：

恩，本文会简要介绍一下NIM取石子游戏与SG函数，并附上一些有趣的例题。

1.简单的取石子游戏

首先，让我们来看一看最简单的取石子游戏。

游戏1
规则：
有x个石子，两人轮流取，最多取y个，不能不取，没得取的人输，两个人都按照最优策略进行游戏，问先手必胜的充要条件。

答案：
x mod (y+1) != 0

恩，刚才那个游戏很简单，下面让我们来看一个稍微难一点的。

游戏2
规则：
有x个石子，两人轮流取，最多取y个，最少取z个，且z<=y，没得取的人输，两个人都按照最优策略进行游戏，问先手必胜的充要条件。

恩，如果大家都没想出来的话。那我就不公布答案了，我其实想借这个问题引入必胜态和必败态的概念。

我们定义必胜态为先手一定能赢的局面，必败态为先手一定不能赢的局面。
然后，对于一个局面，不是必胜态就是必败态（因为没有平局）。
那么显然，对于一个局面a，设B为所以可以转移到局面a的局面的集合。
那么a为必胜态当且仅当存在b属于B，满足b是必败态；
那么a为必败态当且仅当对于所有b属于B，满足b是必胜态。
这个东东的证明是很简单地，如果存在b是必败态，一个聪明的人就会让对方处于必败态，然后自己取胜，如果所有b都是必胜态，那么再怎么聪明的人也只能让对方处于必胜态，然后自己心甘情愿的输掉比赛。

有点无聊，那我们就来点数据吧：
对于游戏2，x=9,y=2,z=4，写出0-9的先手必胜态表，必胜态用W表示，必败态用L表示。
0123456789
LWWWWLLWWW
如果用熟悉的的动态规划来做，那么动规方程就是f[i]=or{!f[j];4>=i-j>=2且j>=0}（f[i]=true表示i为必胜态）。
然后问题再变难一点。

游戏3
规则：
有y个石子，两人轮流取，可以取x个，x属于数集X，没得取的人输，两个人都按照最优策略进行游戏，问哪些是必胜态。

恩，这个问题留给大家思考。

2.基本的NIM取石子游戏

游戏4
规则：
有n堆石子，每堆有xi个石子，两人轮流取，可以在一堆中取任意的石子，但不能不取，也不能跨堆取，没得取的人输，两个人都按照最优策略进行游戏，问哪些是必胜态。

比如有这样3堆：7 11 13。
大家可以先讨论一下。

下面我们引入用异或解NIM取石子问题。
让我们来证明一些东西：
对于a1,a2,...,an，设SG=a1 xor a2 xor ... xor an。

引理1
若SG!=0，那么必然存在0<=k<ai，使得SG xor ai xor k=0，即SG xor ai=k。
即存在0<=(SG xor ai)<ai，显然0<=(SG xor ai)对于1<=i<=n恒成立，我们设SG的二进制最高位为h，那么必然存在ai，满足ai的第h位为1（若不存在，那么SG的h位不可能为1，所以必然存在），这时SG xor ai和ai相比高于h位的地方不会变，而h位变成0了，所以SG xor ai<ai。

引理2
若SG=0，那么不存在0<=k<ai，使得SG xor ai xor k=0，这是显然的，反证法，若存在，那么0 xor ai xor k=0，ai=k，与k<ai矛盾。

下面，我们把异或和NIM联系到一起。
对于一个局面(a1,a2,...,an)，设SG=a1 xor a2 xor ... xor an。
则它为必败态当且仅当SG=0。
首先，我们知道(0,0,...,0)是必败态，这时SG=0，所以命题在这总情况下成立。
然后对于一个局面(a1,a2,...,an)，若a1 xor a2 xor ... xor an != 0，由引理1可知，存在0<=k<ai，使得SG xor ai xor k=0，即a1 xor a2 xor ... xor ai xor ... xor an xor ai xor k=a1 xor a2 xor ... xor k xor ... xor an=0，这就是说，我们可以把ai变成k，使得对方处于一个SG=0的局面(a1,a2,...,k,...,an)。
然后对于一个局面(a1,a2,...,an)，若a1 xor a2 xor ... xor an = 0，由引理2可知，不存在0<=k<ai，使得SG xor ai xor k=0，所以无论如何，都会让对方走到一个SG!=0的局面。
由于棋子数一直在减小，所以最后会结束在SG=0的局面。
若先手处于SG!=0的局面，那么，先手的人会走到一个SG=0的局面，对手又不得不走到一个SG!=0的局面，一直到石子被取完，后手输为止。
若先手处于SG=0的局面，可以同样的分析，先手必败。

3.例题1

例题1（POJ1704[Georgia and Bob]）
题目描述：
两个人玩游戏，在标有1,2,3,4,5...的格子上有一些棋子，规则是选一枚棋子移动，要求不能跨越棋子移动，必需向左移动（可以移动任意格），不能移动的就输掉比赛。
下面是一个棋局的例子：
+--+--+--+--+--+--+--+--+--+
|1x|2 |3x|4 |5 |6x|7x|8 |9 |（旁边标有x的表示在这里有棋子）
+--+--+--+--+--+--+--+--+--+
给出棋子的初始位置，若先手胜，输出"Georgia will win"，否则输出"Bob will win"（不含引号）。
输入格式：
多组数据。
对于每组数据，第一行是有一个T，表示有T组数据。
对于每组数据，第一行有一个N，表示有N枚棋子。
接下来的一行有N个数，分别为每个棋子的位置。
输出格式：
对每组数据，输出一行，如题目描述那样。
样例输入：
2
3
1 2 3
8
1 5 6 7 9 12 14 17
样例输出：
Bob will win
Georgia will win
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
我们从右到左，将每2个棋子看成一对来处理。
如果对方移动某对棋子中的左边棋子x步，那么我方就移动右边棋子x步。
如果对方一定某对棋子中的右边棋子，那么就可以看作NIM游戏了。

4.NIM取石子游戏与SG函数的关系

刚刚我们研究了一下最最朴素的NIM游戏，下面我们要更深入的理解SG函数。
首先SG函数的定义SG(x)=mex({SG(y);x局面可以转变到y局面})，其中mex(X)=min{i;i不属于X且i为自然数}。
先解释一下mex函数，mex函数的参数是一个由一些自然数组成的数集，返回最小的没有出现在这个数集中的自然数，特别的，如果mex作用在空集上，返回的是0。
再解释一下SG函数，SG函数的参数是一个局面，返回一个自然数，就是这个局面的SG值。
首先，对于一个局面x，
如果SG(x)!=0，x可以转移到SG值为0到SG(x)-1的局面，类比NIM游戏，就是当前有SG(x)颗石子，可以取它，剩下0到SG(x)-1颗石子，与此同时x可能转移到某些SG值大于SG(x)的局面y，但是此时对手总可以再将局面y转移回SG值为SG(x)的局面，直至当前选手必选将局面转移到SG值为0到SG(X)-1的局面；
如果SG(x)=0，那么要不是x不能转变到任何状态（必败态），就是x只能转到SG值非0的状态，类比NIM游戏，就是取到0颗后就不能再取了，因为如果能够转到y，那么SG(y)!=0，对方又可以让y转到SG值为0的状态，直至没有前驱。
一个局面x，设y=SG(x)，那么它就相当于有y颗石子的堆。
对于局面(x1,x2,...,xn)，它有子局面x1,x2,...,xn，那么就相当于有n堆石子，分别有SG(x1),SG(x2),...,SG(xn)颗石子。
所以局面(x1,x2,...,xn)为必败态当且仅当SG(x1) xor SG(x2) xor ... xor SG(xn)=0。
并且对于局面(x1,x2,...,xn)不给证明的给出下面的结论，SG((x1,x2,...,xn))=SG(x1) xor SG(x2) xor ... xor SG(xn)。
证明：

对于a1,a2,...,an，设SG=a1 xor a2 xor ... xor an。

引理3
对任意0<=SG'<SG，必然存在0<=k<ai，使得SG xor ai xor k=SG'。
即存在0<=(SG xor ai xor SG')<ai，显然0<=(SG xor ai xor SG')对于1<=i<=n恒成立。
因为SG'<SG，所以必然存在h，SG'的h位为0而SG的h位为1，且高于h位时SG'和SG相同。
这时必然存在ai，满足ai的第h位为1（若不存在，那么SG的h位不可能为1，所以必然存在）。
这时SG xor ai xor SG'和ai相比高于h位的地方不会变，而h位变成0了，所以0<=k=SG xor ai xor SG'<ai。

引理4
不存在0<=k<ai，使得SG xor ai xor k=SG，这是显然的，反证法，若存在，那么SG xor ai xor k=SG，ai=k，与k<ai矛盾。

由引理3和引理4可知对于局面(x1,x2,...xn)，若我们定义SG((x1,x2,...,xn))=SG(x1) xor SG(x2) xor ... xor SG(xn)，则满足SG((x1,x2,...,xn))=mex{SG((x1,x2,...,xn)')}。又因为显然对于任何局面，其SG值是唯一确定的，所以这便是我们要求的局面(x1,x2,...,xn)的SG函数。

然后如果我们用定义来计算在游戏4中，局面(a)的SG值，我们发现SG(a)=a，这就是NIM取石子的神奇之处。

5.例题2

例题2（POJ2960[S-Nim]）
题目描述：
两个人玩游戏，规则是有n堆石子，分别有a1,a2,...,an颗石头，每次从一堆石子中取一些石子，但是可取的石子数是规定了的，必须是{s1,s2,...,sk}中的一个，谁无法操作就输。
输入格式：
多组数据。
对于每组数据，第一行是有一个k，接下来有k个数，分别为s1,s2,...,sk。
第二行有一个数m，表示会给出m个局面。
接下来的m行，先是一个n，然后有n个数，分别为a1,a2,...,an。
若k=0，表示数据结束。
输出格式：
对每组数据，输出一行m个字符组成的字符串，分别表示该组数据中的n个局面是必胜态还是必败态，必胜态用W表示，必败态用L表示。
样例输入：
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
样例输出：
LWW
WWL
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
SG(x)=mex{SG(y);0<=y<x且x-y属于{s1,s2,...,sk}}
SG(GAME)=SG(a1) xor SG(a2) xor ... xor SG(an)

6.例题3

例题3（POJ3537[Crosses and Crosses]）
题目描述：
两个人玩游戏，规则是在标有1,2,3,4,5...，n的格子上画X，一直画一直画，画到有三个X相邻就获胜。
输入格式：
一个数n，就是题目描述中的n。
输出格式：
输出一行，先手胜输出1，否者输出2。
样例输入1：
3
样例输出1：
1
样例输入2：
6
样例输出2：
2
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
+--+--+--+--+--+--+--+--+--+
|.....|AX|BX|CX|DX|EX|.....|
+--+--+--+--+--+--+--+--+--+
如果选手A在CX处画了X，那么显然如果选手B在AX,BX,DX或EX处再画一个X，那么下一步选手A就能获胜，所以选手B要想不输就只能在其他地方画X。
于是游戏n变成了游戏(n-CX-2)和游戏(CX-1-2)，所以SG(n)=mex{SG((n-i-2,i-2-1));i>=3且i<=n-2}=mex{SG(n-i-2)xorSG(i-2-1);i>=3且i<=n-2}。

7.例题4

例题4（POJ2425[A Chess Game]）
题目描述：
两个人玩游戏，规则是给定一个有向无环图，在一些节点上放了棋子，两人轮流移动棋子，每次只能选一颗棋子沿边走一步（一个地方可以放任意多的棋子），最后如果不能走了就输。
输入格式：
多组数据。
每组数据的第一行是N，表示图有N各节点，依次标号为0,1,...,N-1。
接下来的N行，分别表述0,1,..,N-1的出边。
这N行，第一个数x表示出度，接下来的x个数分别为该节点的后继。
接下来有一些询问。
每个询问以一个数M开头，若M=0则表示询问结束，否则有M个数，分别为M个棋子所在的节点编号。
输出格式：
对每个询问，如果是先手必胜输出"WIN"，否者输出"LOSE"（不含引号）。
样例输入：
4
2 1 2
0
1 3
0
1 0
2 0 2
0

4
1 1
1 2
0
0
2 0 1
2 1 1
3 0 1 3
0
样例输出：
WIN
WIN
WIN
LOSE
WIN
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
对于一个棋子SG(x)=max{SG(y);y是x的前驱}。对于m个棋子，SG((x1,x2,...,xm))=SG(x1) xor SG(x2) xor ... xor SG(xm)。

8.例题还有很多

其它题目推荐POJ2975[Nim]，POJ2234[Matches Game]，POJ1067[取石子游戏]，USACO[Holiday 2010 Bonus Competition/glod]rocks。

链接：

《由感性认识到理性认识——透析一类搏弈游戏的解答过程》张一飞国家集训队2002论文
《组合游戏略述——浅谈SG游戏的若干拓展及变形》贾志豪国家集训队2009论文
《Sprague-Grundy Theory》 http://blog.sina.com.cn/s/blog_617615cd0100f6xv.html
《博弈论（二）：Sprague-Grundy 函数定理》 http://hi.baidu.com/yangchenhao/blog/item/c2883f1e70869df01bd57688.html

SGU194[Reactor Cooling]

还是上下界网络流。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-2

DESCRIPTION:

$DESCRIPTION

//Test#1: USACO Training ditch

namespace sj

{

template<int MAXV,int MAXEDGE>

class Relabel_To_Front

{

public:

struct rtf_edge{int v,c;rtf_edge* next;rtf_edge* back;};

struct rtf_list{int u;rtf_list* next;};

typedef struct rtf_edge* edge_pointer;

typedef struct rtf_list* list_pointer;

typedef struct rtf_edge edge;

typedef struct rtf_list list;

static edge_pointer adj[MAXV];

static edge_pointer current[MAXV];

static int e[MAXV];

static int h[MAXV];

static int hn[MAXV*2];

void add_list(int u,list_pointer& tail)

{

static list pool[MAXV];

static list_pointer top=pool;

tail->u=u;

tail->next=top++;

tail=tail->next;

}

static int V,E;

static int s,t;

void add_edge(int u,int v,int c)

{

static edge pool[MAXEDGE];

static edge_pointer top=pool;

top->v=v;

top->c=c;

top->next=adj[u];

adj[u]=top++;

top->v=u;

top->c=0;

top->next=adj[v];

adj[v]=top++;

adj[u]->back=adj[v];

adj[v]->back=adj[u];

}

#define min(a,b) (a)<(b)?(a):(b)

#define relabel(_u)\

/*GAP*/\

hn[h[(_u)]]–;\

if (hn[h[(_u)]]==0&&0<h[(_u)]&&h[(_u)]<V)\

for (int i=0;i<V;i++)\

if (i!=s&&h[(_u)]<h[i]&&h[i]<V+1)\

hn[h[i]]–;\

h[i]=V+1;\

hn[h[i]]++;\

h[(_u)]=V*2-1;\

for (edge_pointer i=adj[(_u)];i;i=i->next)\

if (i->c&&h[(_u)]>h[i->v]+1)\

h[(_u)]=h[i->v]+1;\

/*GAP*/\

hn[h[(_u)]]++;\

}

#define push(_u,_v)\

int df=min(e[(_u)],(_v)->c);\

e[(_u)]-=df;\

e[(_v)->v]+=df;\

(_v)->c-=df;\

(_v)->back->c+=df;\

}

#define discharge(_u)\

while (e[(_u)])\

if (!current[(_u)])\

relabel((_u));\

current[(_u)]=adj[(_u)];\

else if (h[(_u)]==h[current[(_u)]->v]+1\

&&current[(_u)]->c)\

push((_u),current[(_u)]);\

else current[(_u)]=current[(_u)]->next;\

}

int relabel_to_front(void (*build_network)(Relabel_To_Front*))

{

build_network(this);

for (edge_pointer i=adj[s];i;i=i->next)

{

e[s]-=i->c;

e[i->v]+=i->c;

i->back->c=i->c;

i->c=0;

}

h[s]=V;

/*GAP*/

hn[0]=V-1;

hn[V]=1;

list L;

list_pointer head=&L,tail=&L;

for (int i=0;i<V;i++)

if (i!=s&&i!=t)

add_list(i,tail);

for (int i=0;i<V;i++) current[i]=adj[i];

list_pointer pre=0,u=head;

while (u!=tail)

{

int old_h=h[u->u];

discharge(u->u);

if (h[u->u]>old_h)

if (pre)

{

pre->next=u->next;

u->next=head;

head=u;

}

pre=u;

u=u->next;

}

return e[t];

}

#undef min

#undef relabel

#undef push

#undef discharge

};

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::V;

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::E;

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::s;

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::t;

template<int MAXV,int MAXEDGE>

typename Relabel_To_Front<MAXV,MAXEDGE>::edge_pointer

Relabel_To_Front<MAXV,MAXEDGE>::adj[MAXV];

template<int MAXV,int MAXEDGE>

typename Relabel_To_Front<MAXV,MAXEDGE>::edge_pointer

Relabel_To_Front<MAXV,MAXEDGE>::current[MAXV];

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::e[MAXV];

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::h[MAXV];

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::hn[MAXV*2];

}

#include <stdio.h>

#include <string.h>

using namespace sj;

#define MAXN 200

#define MAXM 1000000

typedef Relabel_To_Front<MAXN+2,4*(MAXN+2)*(MAXN+2)> RTF;

int N,M;

int i[MAXM],j[MAXM],lij[MAXM],cij[MAXM];

RTF rtf;

int total;

RTF::edge* f[MAXM];

void build_network(RTF* that)

{

scanf(“%d%d”,&N,&M);

that->V=N+2;

that->s=0;

that->t=N+1;

for (int k=0;k<M;k++)

{

scanf(“%d%d%d%d”,i+k,j+k,lij+k,cij+k);

that->add_edge(that->s,j[k],lij[k]);

that->add_edge(i[k],that->t,lij[k]);

that->add_edge(i[k],j[k],cij[k]-lij[k]);

f[k]=that->adj[j[k]];

total+=lij[k];

}

int main()

{

int flow=rtf.relabel_to_front(build_network);

if (flow!=total) printf(“NO\n”);

else

{

printf(“YES\n”);

for (int k=0;k<M;k++)

printf(“%d\n”,lij[k]+f[k]->c);

}

return 0;

}

SGU176[Flow construction]

上下界网络流，可以去看看胡伯涛的一篇图论的总结。

需要注意的是，数据中有一个点#12，它的最小流是负的（讨论里有一个样例来说明），而题目要求必须大于等于0，所以有点变化。

然后，网络流的实现部分是用的算法导论上讲的Relabel-To-Front实现，我已经把它做成了一个模板。

相比于ISAP，Relabel-To-Front的理论时间复杂度更低，但是ISAP通常很快，甚至有时能和HLPP相媲美，不过我还是选择了Relabel-To-Front。不管怎样，它都比以前学的EK快多了。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-2

DESCRIPTION:

$DESCRIPTION

//Test#1: USACO Training ditch

namespace sj

{

template<int MAXV,int MAXEDGE>

class Relabel_To_Front

{

public:

struct rtf_edge{int v,c;rtf_edge* next;rtf_edge* back;};

struct rtf_list{int u;rtf_list* next;};

typedef struct rtf_edge* edge_pointer;

typedef struct rtf_list* list_pointer;

typedef struct rtf_edge edge;

typedef struct rtf_list list;

static edge_pointer adj[MAXV];

static edge_pointer current[MAXV];

static int e[MAXV];

static int h[MAXV];

static int hn[MAXV*2];

void add_list(int u,list_pointer& tail)

{

static list pool[MAXV];

static list_pointer top=pool;

tail->u=u;

tail->next=top++;

tail=tail->next;

}

static int V,E;

static int s,t;

void add_edge(int u,int v,int c)

{

static edge pool[MAXEDGE];

static edge_pointer top=pool;

top->v=v;

top->c=c;

top->next=adj[u];

adj[u]=top++;

top->v=u;

top->c=0;

top->next=adj[v];

adj[v]=top++;

adj[u]->back=adj[v];

adj[v]->back=adj[u];

}

#define min(a,b) (a)<(b)?(a):(b)

#define relabel(_u)\

/*GAP*/\

hn[h[(_u)]]–;\

if (hn[h[(_u)]]==0&&0<h[(_u)]&&h[(_u)]<V)\

for (int i=0;i<V;i++)\

if (i!=s&&h[(_u)]<h[i]&&h[i]<V+1)\

hn[h[i]]–;\

h[i]=V+1;\

hn[h[i]]++;\

h[(_u)]=V*2-1;\

for (edge_pointer i=adj[(_u)];i;i=i->next)\

if (i->c&&h[(_u)]>h[i->v]+1)\

h[(_u)]=h[i->v]+1;\

/*GAP*/\

hn[h[(_u)]]++;\

}

#define push(_u,_v)\

int df=min(e[(_u)],(_v)->c);\

e[(_u)]-=df;\

e[(_v)->v]+=df;\

(_v)->c-=df;\

(_v)->back->c+=df;\

}

#define discharge(_u)\

while (e[(_u)])\

if (!current[(_u)])\

relabel((_u));\

current[(_u)]=adj[(_u)];\

else if (h[(_u)]==h[current[(_u)]->v]+1\

&&current[(_u)]->c)\

push((_u),current[(_u)]);\

else current[(_u)]=current[(_u)]->next;\

}

int relabel_to_front(void (*build_network)(Relabel_To_Front*))

{

build_network(this);

for (edge_pointer i=adj[s];i;i=i->next)

{

e[s]-=i->c;

e[i->v]+=i->c;

i->back->c=i->c;

i->c=0;

}

h[s]=V;

/*GAP*/

hn[0]=V-1;

hn[V]=1;

list L;

list_pointer head=&L,tail=&L;

for (int i=0;i<V;i++)

if (i!=s&&i!=t)

add_list(i,tail);

for (int i=0;i<V;i++) current[i]=adj[i];

list_pointer pre=0,u=head;

while (u!=tail)

{

int old_h=h[u->u];

discharge(u->u);

if (h[u->u]>old_h)

if (pre)

{

pre->next=u->next;

u->next=head;

head=u;

}

pre=u;

u=u->next;

}

return e[t];

}

#undef min

#undef relabel

#undef push

#undef discharge

};

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::V;

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::E;

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::s;

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::t;

template<int MAXV,int MAXEDGE>

typename Relabel_To_Front<MAXV,MAXEDGE>::edge_pointer

Relabel_To_Front<MAXV,MAXEDGE>::adj[MAXV];

template<int MAXV,int MAXEDGE>

typename Relabel_To_Front<MAXV,MAXEDGE>::edge_pointer

Relabel_To_Front<MAXV,MAXEDGE>::current[MAXV];

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::e[MAXV];

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::h[MAXV];

template<int MAXV,int MAXEDGE>

int Relabel_To_Front<MAXV,MAXEDGE>::hn[MAXV*2];

}

#include <stdio.h>

#include <string.h>

using namespace sj;

#define MAXN 100

#define MAXM 10000

typedef Relabel_To_Front<MAXN+2,4*(MAXN+2)*(MAXN+2)> RTF;

int N,M;

int U[MAXM],V[MAXM],Z[MAXM],C[MAXM];

RTF rtf;

int total;

int first_flow;

RTF::edge* edg1[MAXM];

RTF::edge* edg2[MAXM];

RTF::edge* edg3[MAXM];

RTF::edge* edg4;

void build_network(RTF* that)

{

scanf(“%d%d”,&N,&M);

that->V=N+2;

that->s=0;

that->t=N+1;

for (int i=0;i<M;i++)

{

scanf(“%d%d%d%d”,U+i,V+i,Z+i,C+i);

if (C[i])

{

that->add_edge(that->s,V[i],Z[i]);

that->add_edge(U[i],that->t,Z[i]);

total+=Z[i];

edg1[i]=that->adj[that->s];

edg2[i]=that->adj[U[i]];

}

else

{

that->add_edge(U[i],V[i],Z[i]);

edg3[i]=that->adj[U[i]];

}

const int oo=~(1<<31);

that->add_edge(N,1,oo);

edg4=that->adj[N];

}

void rebuild_network(RTF* that)

{

first_flow=edg4->back->c;

edg4->c=edg4->back->c=0;

for (int i=0;i<M;i++)

if (C[i])

{

edg1[i]->c=edg1[i]->back->c=0;

edg2[i]->c=edg2[i]->back->c=0;

}

memset(RTF::e,0,sizeof(RTF::e));

memset(RTF::h,0,sizeof(RTF::h));

memset(RTF::hn,0,sizeof(RTF::hn));

that->s=0;

that->t=1;

that->V=N+1;

that->add_edge(that->s,N,first_flow);

}

int main()

{

int flow=rtf.relabel_to_front(build_network);

if (flow!=total) printf(“Impossible\n”);

else

{

int flow=rtf.relabel_to_front(rebuild_network);

printf(“%d\n”,first_flow-flow);

for (int i=0;i<M;i++)

if (C[i]) printf(“%d%c”,Z[i],i+1==M?’\n’:’ ‘);

else printf(“%d%c”,edg3[i]->back->c,i+1==M?’\n’:’ ‘);

}

return 0;

}