B http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5552
输入n，表示有n个数1到n。A先拿，B后拿，依次拿，每次可以拿任意一个数，同时会删去这个数的所有因子，最后谁没得拿了谁输。
解法：推了前几个，0，a输，别的a都能赢，证明没想，猜过去的。
网上一个人说的，也不是很清晰：“如果先取的在2-n中取必输,则先取1,
否则则在2-n中取,同时会把1取走，必赢”
#include<cstdio>
int main(){
int n;
while(~scanf("%d",&n)){
puts(n?"win":"fail");
}
return ;
}
E http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5555
n点m边无向图，每个点原来有ai，每个点最终需要bi，有边连就可以把任意个物品移动过去，移动一个物品的花费是1.
解法：最小费用最大流，比赛时建图如下
图中每个点拆成两个点u，u*，源点s连接每一个u，流量是ai，费用为0，ui 到 ui * 流量inf，费用为0， 输入的边在u之间建双向边，流量inf，费用1.
每一个 ui* 连汇点t，流量bi，费用0.
最后最大流要是sum of bi说明存在解，否则-1. 费用只会产生在u之间的边，最小费用就是这个题的答案。
#include<cstdio>
#include<cstring>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
const int M=;
class MaxFlowMinCost { ///最小费用最大流 o(ME)
typedef int typef;///流量的类型
typedef int typec;///费用的类型
static const int ME=2e6+;///边的个数
static const int MV=2e2+;///点的个数
queue<int> q;
int cur[MV],pre[MV];
bool used[MV],sign[MV];
typef flow;
typec cost,dist[MV];
bool spfa(int s,int t) {
mt(used,);
mt(sign,);
mt(dist,);
used[s]=sign[s]=true;
while(!q.empty()) q.pop();
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
used[u]=false;
for(int i=g.head[u]; ~i; i=g.e[i].next) {
if(g.e[i].flow<) continue;
int v=g.e[i].v;
typec c=g.e[i].cost;
if(!sign[v]||dist[v]>dist[u]+c) {
dist[v]=dist[u]+c;
sign[v]=true; pre[v]=u;
cur[v]=i;
if(used[v]) continue;
used[v]=true;
q.push(v);
}
}
}
return sign[t];
} struct G {
struct E {
int v,next;
typef flow;
typec cost;
} e[ME];
int le,head[MV];
void init() {
le=;
mt(head,-);
} void add(int u,int v,typef flow,typec cost) {
e[le].v=v;
e[le].flow=flow;
e[le].cost=cost;
e[le].next=head[u];
head[u]=le++;
}
} g;
public:
void init() {
g.init();
} void add(int u,int v,typef flow,typec cost) {
g.add(u,v,flow,cost);
g.add(v,u,,-cost);
} void solve(int s,int t) {
flow=cost=;
while(spfa(s,t)) {
int temp=t;
typef now=inf;
while(temp!=s) {
now=min(now,g.e[cur[temp]].flow); temp=pre[temp];
}
flow+=now;
temp=t;
while(temp!=s) {
int id=cur[temp];
cost+=now*g.e[id].cost;
g.e[id].flow-=now;
g.e[id^].flow+=now;
temp=pre[temp];
}
}
} typef getflow() {
return flow;
} typec getcost() {
return cost;
}
}mfmc;
int a[M],b[M];
int main() {
int n,m,u,v;
while(~scanf("%d%d",&n,&m)) {
for(int i=; i<=n; i++) {
scanf("%d%d",&a[i],&b[i]);
}
mfmc.init();
int s=n+n+;
int t=s+;
int sum=;
for(int i=;i<=n;i++){
mfmc.add(s,i,a[i],);
mfmc.add(i+n,t,b[i],);
mfmc.add(i,i+n,inf,);
sum+=b[i];
}
while(m--) {
scanf("%d%d",&u,&v);
mfmc.add(u,v,inf,);
mfmc.add(v,u,inf,);
}
mfmc.solve(s,t);
int ans=-;
if(sum==mfmc.getflow()){
ans=mfmc.getcost();
}
printf("%d\n",ans);
}
return ;
}
后来看网上有个建图更好，不用拆点，想想也是，中间流量inf，费用0，那些就直接流过去了，我们可以在脑子把他跑掉，也就是我们只需要对n个点建图，对于输入的边，还是在uv之间建流量inf费用1的双向边，对于a》b的情况，从源点到u连a-b的流，费用0，对于a《b的情况，从u连到汇点t，流量b-a，。a==b的不用连了，这样建图的贪心的默认自己留给自己是最好的，想想也是挺对的。源点出来的流相当于每个点可提供的，流向汇点的相当于每个点的需求。
#include<cstdio>
#include<cstring>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
const int M=;
class MaxFlowMinCost { ///最小费用最大流 o(ME)
typedef int typef;///流量的类型
typedef int typec;///费用的类型
static const int ME=6e2+;///边的个数
static const int MV=1e2+;///点的个数
queue<int> q;
int cur[MV],pre[MV];
bool used[MV],sign[MV];
typef flow;
typec cost,dist[MV];
bool spfa(int s,int t) {
mt(used,);
mt(sign,);
mt(dist,);
used[s]=sign[s]=true;
while(!q.empty()) q.pop();
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
used[u]=false;
for(int i=g.head[u]; ~i; i=g.e[i].next) {
if(g.e[i].flow<) continue;
int v=g.e[i].v;
typec c=g.e[i].cost;
if(!sign[v]||dist[v]>dist[u]+c) {
dist[v]=dist[u]+c;
sign[v]=true; pre[v]=u;
cur[v]=i;
if(used[v]) continue;
used[v]=true;
q.push(v);
}
}
}
return sign[t];
} struct G {
struct E {
int v,next;
typef flow;
typec cost;
} e[ME];
int le,head[MV];
void init() {
le=;
mt(head,-);
} void add(int u,int v,typef flow,typec cost) {
e[le].v=v;
e[le].flow=flow;
e[le].cost=cost;
e[le].next=head[u];
head[u]=le++;
}
} g;
public:
void init() {
g.init();
} void add(int u,int v,typef flow,typec cost) {
g.add(u,v,flow,cost);
g.add(v,u,,-cost);
} void solve(int s,int t) {
flow=cost=;
while(spfa(s,t)) {
int temp=t;
typef now=inf;
while(temp!=s) {
now=min(now,g.e[cur[temp]].flow); temp=pre[temp];
}
flow+=now;
temp=t;
while(temp!=s) {
int id=cur[temp];
cost+=now*g.e[id].cost;
g.e[id].flow-=now;
g.e[id^].flow+=now;
temp=pre[temp];
}
}
} typef getflow() {
return flow;
} typec getcost() {
return cost;
}
}mfmc;
int a[M],b[M];
int main() {
int n,m,u,v;
while(~scanf("%d%d",&n,&m)) {
for(int i=; i<=n; i++) {
scanf("%d%d",&a[i],&b[i]);
}
mfmc.init();
int s=;
int t=n+;
int sum=;
for(int i=;i<=n;i++){
if(a[i]>b[i]){
mfmc.add(s,i,a[i]-b[i],);
}
else if(a[i]<b[i]){
mfmc.add(i,t,b[i]-a[i],);
sum+=b[i]-a[i];
}
}
while(m--) {
scanf("%d%d",&u,&v);
mfmc.add(u,v,inf,);
mfmc.add(v,u,inf,);
}
mfmc.solve(s,t);
int ans=-;
if(sum==mfmc.getflow()){
ans=mfmc.getcost();
}
printf("%d\n",ans);
}
return ;
}
end