HDU 1565
方格取数(1)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5961 Accepted Submission(s): 2268
Problem Description
给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
Input
包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例，输出可能取得的最大的和
Sample Input
3
75 15 21
75 15 28
34 70 5
Sample Output
188
最大点权独立集
弱弱的EK算法
邻接矩阵实现 124MS
邻接表实现 15MS
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <set> #include <string> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; #define INF 0x3f3f3f3f #define ll long long #define N 510 int n; int src; int des; int sum; int pre[N]; int mpt[N][N]; int map[N][N]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; queue<int> q; bool bfs() { while(!q.empty()) q.pop(); memset(pre,-1,sizeof(pre)); pre[src]=0; q.push(src); while(!q.empty()) { int u=q.front(); q.pop(); for(int v=0;v<=n*n+1;v++) { if(pre[v]==-1 && mpt[u][v]>0) { pre[v]=u; if(v==des) return 1; q.push(v); } } } return 0; } int EK() { int maxflow=0; while(bfs()) { int minflow=INF; for(int i=des;i!=src;i=pre[i]) minflow=min(minflow,mpt[pre[i]][i]); maxflow+=minflow; for(int i=des;i!=src;i=pre[i]) { mpt[pre[i]][i]-=minflow; mpt[i][pre[i]]+=minflow; } } return maxflow; } int main() { int i,j,k; while(scanf("%d",&n)!=EOF) { sum=0; memset(mpt,0,sizeof(mpt)); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&map[i][j]); sum+=map[i][j]; } } src=0; des=n*n+1; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if((i+j)%2==0) mpt[src][(i-1)*n+j]=map[i][j]; else mpt[(i-1)*n+j][des]=map[i][j]; } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if((i+j)%2==0) { for(k=0;k<4;k++) { int x=i+dir[k][0]; int y=j+dir[k][1]; if(x>=1 && x<=n && y>=1 && y<=n) { mpt[(i-1)*n+j][(x-1)*n+y]=INF; } } } } } printf("%d ",sum-EK()); } return 0; }
HDU 1569
和方格取数1数据大小不一样，用上面的会超时，可能是写搓了。
邻接表实现 280ms
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <set> #include <string> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; #define INF 0x3f3f3f3f #define ll long long #define N 20510 struct Edge { int to,next,val; }edge[N]; int tot; int head[N]; int n; int m; int src; int des; int sum; int pre[N]; int path[N]; int map[N][N]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; queue<int> q; void init() { tot=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w) { edge[tot].to=v; edge[tot].val=w; edge[tot].next=head[u]; head[u]=tot++; edge[tot].to=u; edge[tot].val=0; edge[tot].next=head[v]; head[v]=tot++; } bool bfs() { while(!q.empty()) q.pop(); memset(pre,-1,sizeof(pre)); pre[src]=0; q.push(src); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(pre[v]==-1 && edge[i].val>0) { pre[v]=u; path[v]=i; if(v==des) return 1; q.push(v); } } } return 0; } int EK() { int maxflow=0; while(bfs()) { int minflow=INF; for(int i=des;i!=src;i=pre[i]) minflow=min(minflow,edge[path[i]].val); maxflow+=minflow; for(int i=des;i!=src;i=pre[i]) { edge[path[i]].val-=minflow; edge[path[i]^1].val+=minflow; } } return maxflow; } int main() { int i,j,k; while(scanf("%d%d",&n,&m)!=EOF) { sum=0; init(); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&map[i][j]); sum+=map[i][j]; } } src=0; des=n*m+1; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if((i+j)%2==0) add(src,(i-1)*m+j,map[i][j]); else add((i-1)*m+j,des,map[i][j]); } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if((i+j)%2==0) { for(k=0;k<4;k++) { int x=i+dir[k][0]; int y=j+dir[k][1]; if(x>=1 && x<=n && y>=1 && y<=m) { add((i-1)*m+j,(x-1)*m+y,INF); } } } } } printf("%d ",sum-EK()); } return 0; }