这个题网上很多人都说用状态压缩dp来做，我就是觉得状态压缩dp有点那么理解不上啊，不过如果这个题吧相邻的两个格子连起来，那不就是求最大权独立点集吗？奋战了三天，我的第一道最大流题目终于写出来了，高兴啊！
#include #include<set> #include #include #include #include #include #include<string> #include #include #include #include #define inf 0x0f0f0f0f using namespace std; const double pi=acos(-1.0); const double eps=1e-8; typedef pair<int,int>pii; const int maxn=2500+10; struct Edge { int from,to,cap,flow; }; int n,m,s,t; vectoredges; vector<int>G[maxn]; int d[maxn],cur[maxn]; bool vis[maxn]; void AddEdge(int from,int to,int cap) { Edge temp; temp.cap=cap; temp.flow=0; temp.from=from; temp.to=to; edges.push_back(temp); temp.cap=0; temp.flow=0; temp.from=to; temp.to=from; edges.push_back(temp); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front();Q.pop(); for (int i=0;i) { Edge& e=edges[G[x][i]]; if (!vis[e.to] && e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if (x==t || a==0) return a; int flow=0,f; for (int i=cur[x];i) { Edge& e=edges[G[x][i]]; if (d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if (a==0) break; } } return flow; } int Dinic() { int flow=0; while (BFS()) { memset(cur,0,sizeof(cur)); flow+=DFS(s,inf); } return flow; } void init() { for (int i=0;i<=maxn;i++) G[i].clear(); edges.clear(); } int main() { //freopen("in.txt","r",stdin); int N,M,a,sum; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; while (scanf("%d",&N)!=EOF) { init(); s=0;t=N*N+1; sum=0; for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) { scanf("%d",&a); sum+=a; int x=(i-1)*N+j; if ((i+j)%2==0) { AddEdge(s,x,a); for (int k=0;k<4;k++) { int xx=i+dx[k]; int yy=j+dy[k]; if (xx>=1 && xx<=N && yy>=1 && yy<=N) { int y=(xx-1)*N+yy; AddEdge(x,y,inf); } } } else { AddEdge(x,t,a); for (int k=0;k<4;k++) { int xx=i+dx[k]; int yy=j+dy[k]; if (xx>=1 && xx<=N && yy>=1 && yy<=N) { int y=(xx-1)*N+yy; AddEdge(y,x,inf); } } } } printf("%d\n",sum-Dinic()); } //fclose(stdin); return 0; }
京公网安备 11010802041100号