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取走,必赢”
1 #include<cstdio> 2 int main(){ 3 int n; 4 while(~scanf("%d",&n)){ 5 puts(n?"win":"fail"); 6 } 7 return 0; 8 }
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之间的边,最小费用就是这个题的答案。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 const int M=110; 8 class MaxFlowMinCost { ///最小费用最大流 o(ME) 9 typedef int typef;///流量的类型 10 typedef int typec;///费用的类型 11 static const int ME=2e6+10;///边的个数 12 static const int MV=2e2+10;///点的个数 13 queue<int> q; 14 int cur[MV],pre[MV]; 15 bool used[MV],sign[MV]; 16 typef flow; 17 typec cost,dist[MV]; 18 bool spfa(int s,int t) { 19 mt(used,0); 20 mt(sign,0); 21 mt(dist,0); 22 used[s]=sign[s]=true; 23 while(!q.empty()) q.pop(); 24 q.push(s); 25 while(!q.empty()) { 26 int u=q.front(); 27 q.pop(); 28 used[u]=false; 29 for(int i=g.head[u]; ~i; i=g.e[i].next) { 30 if(g.e[i].flow<1) continue; 31 int v=g.e[i].v; 32 typec c=g.e[i].cost; 33 if(!sign[v]||dist[v]>dist[u]+c) { 34 dist[v]=dist[u]+c; 35 sign[v]=true; 36 37 pre[v]=u; 38 cur[v]=i; 39 if(used[v]) continue; 40 used[v]=true; 41 q.push(v); 42 } 43 } 44 } 45 return sign[t]; 46 } struct G { 47 struct E { 48 int v,next; 49 typef flow; 50 typec cost; 51 } e[ME]; 52 int le,head[MV]; 53 void init() { 54 le=0; 55 mt(head,-1); 56 } void add(int u,int v,typef flow,typec cost) { 57 e[le].v=v; 58 e[le].flow=flow; 59 e[le].cost=cost; 60 e[le].next=head[u]; 61 head[u]=le++; 62 } 63 } g; 64 public: 65 void init() { 66 g.init(); 67 } void add(int u,int v,typef flow,typec cost) { 68 g.add(u,v,flow,cost); 69 g.add(v,u,0,-cost); 70 } void solve(int s,int t) { 71 flow=cost=0; 72 while(spfa(s,t)) { 73 int temp=t; 74 typef now=inf; 75 while(temp!=s) { 76 now=min(now,g.e[cur[temp]].flow); 77 78 temp=pre[temp]; 79 } 80 flow+=now; 81 temp=t; 82 while(temp!=s) { 83 int id=cur[temp]; 84 cost+=now*g.e[id].cost; 85 g.e[id].flow-=now; 86 g.e[id^1].flow+=now; 87 temp=pre[temp]; 88 } 89 } 90 } typef getflow() { 91 return flow; 92 } typec getcost() { 93 return cost; 94 } 95 }mfmc; 96 int a[M],b[M]; 97 int main() { 98 int n,m,u,v; 99 while(~scanf("%d%d",&n,&m)) { 100 for(int i=1; i<=n; i++) { 101 scanf("%d%d",&a[i],&b[i]); 102 } 103 mfmc.init(); 104 int s=n+n+1; 105 int t=s+1; 106 int sum=0; 107 for(int i=1;i<=n;i++){ 108 mfmc.add(s,i,a[i],0); 109 mfmc.add(i+n,t,b[i],0); 110 mfmc.add(i,i+n,inf,0); 111 sum+=b[i]; 112 } 113 while(m--) { 114 scanf("%d%d",&u,&v); 115 mfmc.add(u,v,inf,1); 116 mfmc.add(v,u,inf,1); 117 } 118 mfmc.solve(s,t); 119 int ans=-1; 120 if(sum==mfmc.getflow()){ 121 ans=mfmc.getcost(); 122 } 123 printf("%d ",ans); 124 } 125 return 0; 126 }
后来看网上有个建图更好,不用拆点,想想也是,中间流量inf,费用0,那些就直接流过去了,我们可以在脑子把他跑掉,也就是我们只需要对n个点建图,对于输入的边,还是在uv之间建流量inf费用1的双向边,对于a》b的情况,从源点到u连a-b的流,费用0,对于a《b的情况,从u连到汇点t,流量b-a,。a==b的不用连了,这样建图的贪心的默认自己留给自己是最好的,想想也是挺对的。源点出来的流相当于每个点可提供的,流向汇点的相当于每个点的需求。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 const int M=110; 8 class MaxFlowMinCost { ///最小费用最大流 o(ME) 9 typedef int typef;///流量的类型 10 typedef int typec;///费用的类型 11 static const int ME=6e2+10;///边的个数 12 static const int MV=1e2+10;///点的个数 13 queue<int> q; 14 int cur[MV],pre[MV]; 15 bool used[MV],sign[MV]; 16 typef flow; 17 typec cost,dist[MV]; 18 bool spfa(int s,int t) { 19 mt(used,0); 20 mt(sign,0); 21 mt(dist,0); 22 used[s]=sign[s]=true; 23 while(!q.empty()) q.pop(); 24 q.push(s); 25 while(!q.empty()) { 26 int u=q.front(); 27 q.pop(); 28 used[u]=false; 29 for(int i=g.head[u]; ~i; i=g.e[i].next) { 30 if(g.e[i].flow<1) continue; 31 int v=g.e[i].v; 32 typec c=g.e[i].cost; 33 if(!sign[v]||dist[v]>dist[u]+c) { 34 dist[v]=dist[u]+c; 35 sign[v]=true; 36 37 pre[v]=u; 38 cur[v]=i; 39 if(used[v]) continue; 40 used[v]=true; 41 q.push(v); 42 } 43 } 44 } 45 return sign[t]; 46 } struct G { 47 struct E { 48 int v,next; 49 typef flow; 50 typec cost; 51 } e[ME]; 52 int le,head[MV]; 53 void init() { 54 le=0; 55 mt(head,-1); 56 } void add(int u,int v,typef flow,typec cost) { 57 e[le].v=v; 58 e[le].flow=flow; 59 e[le].cost=cost; 60 e[le].next=head[u]; 61 head[u]=le++; 62 } 63 } g; 64 public: 65 void init() { 66 g.init(); 67 } void add(int u,int v,typef flow,typec cost) { 68 g.add(u,v,flow,cost); 69 g.add(v,u,0,-cost); 70 } void solve(int s,int t) { 71 flow=cost=0; 72 while(spfa(s,t)) { 73 int temp=t; 74 typef now=inf; 75 while(temp!=s) { 76 now=min(now,g.e[cur[temp]].flow); 77 78 temp=pre[temp]; 79 } 80 flow+=now; 81 temp=t; 82 while(temp!=s) { 83 int id=cur[temp]; 84 cost+=now*g.e[id].cost; 85 g.e[id].flow-=now; 86 g.e[id^1].flow+=now; 87 temp=pre[temp]; 88 } 89 } 90 } typef getflow() { 91 return flow; 92 } typec getcost() { 93 return cost; 94 } 95 }mfmc; 96 int a[M],b[M]; 97 int main() { 98 int n,m,u,v; 99 while(~scanf("%d%d",&n,&m)) { 100 for(int i=1; i<=n; i++) { 101 scanf("%d%d",&a[i],&b[i]); 102 } 103 mfmc.init(); 104 int s=0; 105 int t=n+1; 106 int sum=0; 107 for(int i=1;i<=n;i++){ 108 if(a[i]>b[i]){ 109 mfmc.add(s,i,a[i]-b[i],0); 110 } 111 else if(a[i]<b[i]){ 112 mfmc.add(i,t,b[i]-a[i],0); 113 sum+=b[i]-a[i]; 114 } 115 } 116 while(m--) { 117 scanf("%d%d",&u,&v); 118 mfmc.add(u,v,inf,1); 119 mfmc.add(v,u,inf,1); 120 } 121 mfmc.solve(s,t); 122 int ans=-1; 123 if(sum==mfmc.getflow()){ 124 ans=mfmc.getcost(); 125 } 126 printf("%d ",ans); 127 } 128 return 0; 129 }
end