给出一个 (n×m) ( n × m ) 棋盘，其中有一些格子是城市，有部分城市是重要区域，要求在城市中修轨道，要求： 轨道只能放在城市之中，并且每个轨道需要与相邻的四个格子中的两个相连， 需要使每个城市都有轨道，不是城市的地方不能有轨道，城市之间不需要联通。
重要区域的轨道要尽量弯曲，即重要区域的轨道需要连接一横一纵两个方向。现在定义一种方案的代价为：重要区域直行轨道的数量。
给出这个棋盘，求出最小代价。 n,m≤25 n , m ≤ 25
首先，必须知道棋盘在图论算法中，是一个经典的模型：每个棋盘都是一个完美的二分图，设棋盘上某个点的坐标为 (x,y) ( x , y ) ，根据 (x+y)mod 2 ( x + y ) m o d 2 的值，将棋盘分为两部分。这就形成了一个二分图。
再回到这道题上来，题目要求：使得每个轨道需要与周围的某两个轨道相连。先忽略重要地区的问题，比较套路的做法是： 将两类点分别设为A，B，只需要 s s 向每个A中的点连一条容量为2的边，每条B的节点再向tt连一条容量为2的边。每个A类点向其周围的B类点分别连一条容量为1的边。这样如果能够满流，即可判定至少存在一种合法方案。
现在，要加入重要地区： 题目中说，若重要地区的轨道为直，就要1的代价。 这时候，就需要用到网络流建模中，最基本的技巧：拆点 我们将每个点一分为三，如下图所示： 不重要的A类城市： 重要的A类城市： 不重要的B类城市 重要的B类城市： 跑费用流即可，同样是判断是否满流，同时求出最小费用即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<iostream> #define SF scanf #define PF printf #define MAXN 2010 #define MAXM 30 #define INF 0x3FFFFFFF using namespace std; int s,t,n,m; int fa[MAXN],id[MAXN],idx[MAXM][MAXM][5],d[MAXN]; int wx[5][3]={{0,1},{-1,0},{0,-1},{1,0}}; bool vis[MAXN]; vector<int> a[MAXN],w[MAXN],c[MAXN],rev[MAXN]; vector<string> mp,mpr; string mp1; bool spfa(){ memset(vis,0,sizeof vis); memset(d,0x3f3f3f3f,sizeof d); queue<int>q; vis[s]=1; fa[s]=s; d[s]=0; q.push(s); while(!q.empty()){ int fnt=q.front(); q.pop(); vis[fnt]=0; for(int i=0;i<a[fnt].size();i++){ int v=a[fnt][i]; if(w[fnt][i]&&d[v]>d[fnt]+c[fnt][i]){ d[v]=d[fnt]+c[fnt][i]; fa[v]=fnt; id[v]=i; if(vis[v]==0){ vis[v]=1; q.push(v); } } } } if(d[t]==0x3f3f3f3f) return 0; return 1; } pair<int,int> solve(){ int res=0,ans=0; while(spfa()){ int minf=INF; for(int i=t;i!=s;i=fa[i]) minf=min(minf,w[fa[i]][id[i]]); res+=minf; for(int i=t;i!=s;i=fa[i]){ w[fa[i]][id[i]]-=minf; w[i][rev[fa[i]][id[i]]]+=minf; ans+=c[fa[i]][id[i]]*minf; } } return make_pair(res,ans); } void addlink(int x,int y,int len,int cot){ a[x].push_back(y); a[y].push_back(x); w[x].push_back(len); w[y].push_back(0); c[x].push_back(cot); c[y].push_back(-cot); rev[x].push_back(a[y].size()-1); rev[y].push_back(a[x].size()-1); } void addedge(int x,int y,int flag){ if((x+y)%2==0){ addlink(s,idx[x][y][0],2,0); if(flag){ addlink(idx[x][y][0],idx[x][y][1],1,0); addlink(idx[x][y][0],idx[x][y][1],1,1); addlink(idx[x][y][0],idx[x][y][2],1,0); addlink(idx[x][y][0],idx[x][y][2],1,1); } else{ addlink(idx[x][y][0],idx[x][y][1],2,0); addlink(idx[x][y][0],idx[x][y][2],2,0); } } else{ addlink(idx[x][y][0],t,2,0); if(flag){ addlink(idx[x][y][1],idx[x][y][0],1,0); addlink(idx[x][y][1],idx[x][y][0],1,1); addlink(idx[x][y][2],idx[x][y][0],1,0); addlink(idx[x][y][2],idx[x][y][0],1,1); } else{ addlink(idx[x][y][1],idx[x][y][0],2,0); addlink(idx[x][y][2],idx[x][y][0],2,0); } } for(int i=0;i<4;i++){ int xx=x+wx[i][0]; int yy=y+wx[i][1]; if(xx<0||yy<0||xx>=n||yy>=m) continue; if(mp[xx][yy]=='w') continue; if((x+y)%2==0) addlink(idx[x][y][i%2+1],idx[xx][yy][i%2+1],1,0); } } class CurvyonRails{ public: int getmin(vector<string> &mpx){ /*SF("%d",&n); for(int i=0;i<n;i++){ cin>>mp1; mp.push_back(mp1); }*/ mp=mpx; n=mp.size(); m=mp[0].size(); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ idx[i][j][0]=i*m+j; idx[i][j][1]=i*m+j+n*m; idx[i][j][2]=i*m+j+n*m*2; } s=3*n*m; t=3*n*m+1; int cnt=0,cnt1=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++){ if(mp[i][j]=='w') continue; if((i+j)%2==0) cnt++; else cnt1++; if(mp[i][j]=='C'){ addedge(i,j,1); } else{ addedge(i,j,0); } } pair<int,int> ans=solve(); if(ans.first!=cnt*2||cnt!=cnt1) return -1; else return ans.second; } }; /*int main(){ SF("%d",&n); for(int i=0;i<n;i++){ cin>>mp1; mpr.push_back(mp1); } PF("%d",sbcch.getmin(mpr)); }*/