首页 > 代码库 > XTU 二分图和网络流 练习题 C. 方格取数(1)
XTU 二分图和网络流 练习题 C. 方格取数(1)
C. 方格取数(1)
Time Limit: 5000ms
Memory Limit: 32768KB
64-bit integer IO format: %I64d Java class name: Main给你一个n*n的格子的棋盘,每个格子里面有一个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
Input
包括多个测试实例,每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例,输出可能取得的最大的和
Sample Input
375 15 21 75 15 28 34 70 5
Sample Output
188
解题:有人用状态压缩dp做啊,我只能对着别人的代码敲了。。。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #define LL long long13 #define INF 0x3f3f3f3f14 using namespace std;15 const int maxn = 510;16 int mp[maxn*maxn],tot,n,src,sink;17 int c[maxn][maxn];18 bool vis[maxn];19 int dfs(int u,int low){20 if(u == sink) return low;21 if(vis[u]) return 0;22 vis[u] = true;23 for(int v = 0,flow; v <= sink; v++){24 if(c[u][v] && (flow = dfs(v,min(low,c[u][v])))){25 c[u][v] -= flow;26 c[v][u] += flow;27 return flow;28 }29 }30 return 0;31 }32 int maxFlow(){33 int ans = 0,flow;34 memset(vis,false,sizeof(vis));35 while(flow = dfs(src,INF)){36 memset(vis,false,sizeof(vis));37 ans += flow;38 }39 return ans;40 }41 int main(){42 int i,j,temp;43 while(~scanf("%d",&n)){44 j = n*n;45 src = http://www.mamicode.com/tot = 0;46 sink = j+1;47 memset(mp,0,sizeof(mp));48 memset(c,0,sizeof(c));49 for(i = 1; i <= j; i++){50 scanf("%d",&temp);51 tot += temp;52 if(i <= n) mp[i] = !mp[i-1];53 else mp[i] = !mp[i-n];54 if(mp[i]){55 if(i%n) c[i][i+1] = INF;//右边56 if(i%n != 1) c[i][i-1] = INF;//左边57 if(i <= n*(n-1)) c[i][n+i] = INF;//下边58 if(i > n) c[i][i-n] = INF;//上边59 c[src][i] = temp;60 }else c[i][sink] = temp;61 }62 printf("%d\n",tot-maxFlow());63 }64 return 0;65 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。