COJ 0501 取数游戏（TPM）

取数游戏（TPM）

难度级别：D；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

给你一个n*n的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能有公共边，并且取出的数的和最大。（二分图匹配练习）

输入

第一行是一个正整数n (n<20)。
接下来是 n*n 个非负数。

输出

输出可能取得的最大的和。

输入示例

3
5 9 4
8 3 6
2 7 1

输出示例

其他说明

n<20

题解：“没有公共边”这是赤裸裸的二分图呀！随便按(i+j)&1造个二分图跑了就行。。。

而且，这是我第一个接触的构造题吧= = 还是非常有纪念意义的= =我记得当年还是小健建给我亲自敲了一遍DInic然后敲了一遍这道题。。。回忆满满呢~

现在老练的ISAP+缩行：

 1 //这两道题有什么区别。。。= =
 2 #include<iostream>   
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cstring>
 8 using namespace std;
 9 const int maxn=2002+10,maxm=80002+10,inf=-1u>>1;
10 struct ISAP{
11     struct tedge{int x,y,w,next;}adj[maxm];int ms,fch[maxn];
12     int d[maxn],s[maxn],cur[maxn],gap[maxn],n,top;
13     void init(int n){
14         this->n=n;ms=0;top=0;
15         memset(d,-1,sizeof(d));
16         memset(fch,-1,sizeof(fch));
17         return;
18     }
19     void addedge(int u,int v,int w){
20         adj[ms]=(tedge){u,v,w,fch[u]};fch[u]=ms++;
21         adj[ms]=(tedge){v,u,0,fch[v]};fch[v]=ms++;
22         return;
23     }
24     void bfs(){
25         queue<int>Q;Q.push(n);d[n]=0;
26         while(!Q.empty()){
27             int u=Q.front();Q.pop();
28             for(int i=fch[u];i!=-1;i=adj[i].next){
29                 int v=adj[i].y;
30                 if(d[v]==-1) d[v]=d[u]+1,Q.push(v);
31             }
32         } return;
33     }
34     int maxflow(int S,int T){
35         n=T;bfs();int k=S,i,flow=0;
36         for(i=0;i<=n;i++) cur[i]=fch[i],gap[d[i]]++;
37         while(d[S]<n){
38             if(k==n){
39                 int mi=inf,pos;
40                 for(i=0;i<top;i++) if(adj[s[i]].w<mi) mi=adj[s[i]].w,pos=i;
41                 for(i=0;i<top;i++) adj[s[i]].w-=mi,adj[s[i]^1].w+=mi;
42                 flow+=mi;top=pos;k=adj[s[top]].x;
43             }
44             for(i=cur[k];i!=-1;i=adj[i].next){
45                 int v=adj[i].y;
46                 if(adj[i].w&&d[k]==d[v]+1){cur[k]=i;k=v;s[top++]=i;break;}
47             }
48             if(i==-1){
49                 int lim=n;
50                 for(i=fch[k];i!=-1;i=adj[i].next){
51                     int v=adj[i].y;
52                     if(adj[i].w&&d[v]<lim) lim=d[v],cur[k]=i;
53                 } if(--gap[d[k]]==0) break;
54                 d[k]=lim+1;gap[d[k]]++;
55                 if(k!=S) k=adj[s[--top]].x;
56             }
57         } return flow;
58     }
59 }sol;
60 inline int read(){
61     int x=0,sig=1;char ch=getchar();
62     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
63     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
64     return x*=sig;
65 }
66 inline void write(int x){
67     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
68     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
69     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
70 }
71 int A[21][21],mx[]={1,-1,0,0},my[]={0,0,-1,1};
72 void init(){
73     int n=read();long long ans=0;
74     sol.init(n*n+2);int S=n*n+1,T=n*n+2;
75     for(int i=1;i<=n;i++)
76        for(int j=1;j<=n;j++){
77                A[i][j]=read();
78             if((i+j)&1){
79                sol.addedge(S,i*n+j-n,A[i][j]);
80                for(int d=0;d<4;d++){
81                    int nx=i+mx[d],ny=j+my[d];
82                    if(nx>=1&&nx<=n&&ny>=1&&ny<=n) sol.addedge(i*n+j-n,nx*n+ny-n,inf);
83                }
84            }
85            else sol.addedge(i*n+j-n,T,A[i][j]);
86            ans+=A[i][j];
87        } 
88     write(ans-sol.maxflow(S,T));
89     return;
90 }
91 void work(){
92     return;
93 }
94 void print(){
95     return;
96 }
97 int main(){
98     init();work();print();return 0;
99 }

当时最稚嫩的代码。。。真的有种说不出的感动：

  1 #include <iostream>
  2 #include <queue>
  3 using namespace std;
  4 
  5 const int maxn = 400 + 10;
  6 const int maxm = 10000 + 10;
  7 
  8 struct Edge
  9 {
 10     int from, to, cap, flow;
 11 };
 12 
 13 struct Dinic
 14 {
 15     int n, m, s, t;
 16     int first[maxn], next[maxm];
 17     
 18     Edge edges[maxm];
 19     
 20     void init(int n)
 21     {
 22         this -> n = n;
 23         m = 0;
 24         
 25         memset(first, -1, sizeof(first));
 26         
 27         return ;
 28     }
 29     
 30     void AddEdge(int from, int to, int cap)
 31     {
 32         edges[m] = (Edge){from, to, cap, 0};
 33         next[m] = first[from];
 34         first[from] = m++;
 35         
 36         edges[m] = (Edge){to, from, 0, 0};
 37         next[m] = first[to];
 38         first[to] = m++;
 39         
 40         return ;
 41     }
 42     
 43     int d[maxn], cur[maxn];
 44     bool vis[maxn];
 45     
 46     int BFS()
 47     {
 48         memset(vis, 0, sizeof(vis));
 49         queue<int> Q;
 50         
 51         Q.push(s);
 52         vis[s] = true;
 53         d[s] = 0;
 54         
 55         
 56         
 57         while(!Q.empty())
 58         {
 59             int x = Q.front(); Q.pop();
 60             
 61             for(int i = first[x]; i != -1; i = next[i])
 62             {
 63                 Edge& e = edges[i];
 64                 if(!vis[e.to] && e.cap > e.flow)
 65                 {
 66                     vis[e.to] = true;
 67                     d[e.to] = d[x] + 1;
 68                     Q.push(e.to);
 69                 }
 70             }
 71         }
 72             
 73         return vis[t];
 74     }
 75     int DFS(int x, int a)
 76     {
 77         if(x == t || !a) return a;
 78         
 79         int f, flow = 0;
 80         
 81         for(int& i = cur[x]; i != -1; i = next[i])
 82         {
 83             Edge& e = edges[i];
 84             if(d[e.to] == d[x] + 1 && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0)
 85             {
 86                 flow += f;
 87                 a -= f;
 88                 e.flow += f;
 89                 edges[i ^ 1].flow -= f;
 90                 if(!a) break;
 91             }
 92         }
 93         return flow;
 94     }
 95     
 96     
 97     int MaxFlow(int s, int t)
 98     {
 99         this -> s = s;
100         this -> t = t;
101         
102         int flow = 0;
103         
104         while(BFS())
105         {
106             for(int i = 0; i < n; i++) cur[i] = first[i];
107             flow += DFS(s, 1000000000);
108         }
109         return flow;   //你大爷！！！！！！！！！！！！！！！！ 
110     }
111 }sol;
112 
113 int a[21][21];
114 int nx[] = {0, 0, -1, 1};
115 int ny[] = {-1, 1, 0, 0};
116 
117 int main()
118 {
119     int n, m;
120     scanf("%d", &n);
121     
122     m = n;
123     
124     sol.init(n * m + 2);
125     
126     long long double tot = 0;
127     
128     int s = n * m;
129     int t = n * m + 1;
130     
131     for(int i = 0; i < n; i++)
132       for(int j = 0; j < m; j++)
133       {
134           scanf("%d", &a[i][j]);
135           tot += a[i][j];
136           if((i + j) & 1)
137           {
138               sol.AddEdge(s, i * m + j, a[i][j]);
139               
140               
141               for(int d = 0; d < 4; d++)
142               {
143                   int mx = nx[d] + i;
144                   int my = ny[d] + j;
145                   
146                   if(mx >= 0 && mx < n && my >= 0 && my < m)
147                   {
148                       sol.AddEdge(i * m + j, mx * m + my, 2000000000);
149                   }
150               }
151           }
152           else sol.AddEdge(i * m + j, t, a[i][j]);
153       }
154       
155     printf("%d
", tot - sol.MaxFlow(s, t)); 156     
157     //system("pause");
158     return 0;
159 }