TopCoder SRM 570 Div1 CurvyonRails

题意: 一个$n\times m$的网格图，其中有一些点需要建铁路，有一些点为关键点，在关键点上修直铁路会产生1的代价，求最小的代价

由于$n,m\leq 25$显然不可以插头$\text{dp}$。。。

考虑轨道联通实际上类似网络流的形式

考虑一个常见的思路: 网格图可以简化为二分图 然后 跑网络流

先不考虑代价的问题，判断是否存在合法方案

每个格子要有两条出边，因此可以让$S$向左侧点连边权为2的边，右侧点向$T$连边权为2的边

然后可以让每个左侧点向相邻的右侧点连边，即考虑了联通关系

下面考虑代价的计算，加入边的代价，即为费用流

连同向边会产生代价，因此考虑为每个节点新增两个节点，表示向上下/左右连边

对于让原节点对于新增的上下和左右节点 分别连两条代价为0和1的边

这样如果流了同向边，就会产生代价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int,int> Pii;
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=25*30*3,M=N<<3,INF=1e9+10;

int n,m,k;
int a[30][30];

// Max Flow Min Cost

int id[30][30][2];
struct Edge{
	int to,nxt,w,c;
}e[M];
int head[N],ecnt,S,T,V;
void Clear(){
	rep(i,1,V) head[i]=0;
	ecnt=1,V=0;
}
void AddEdge(int u,int v,int w,int c) {
	e[++ecnt]=(Edge){v,head[u],w,c};
	head[u]=ecnt;
}
void Link(int u,int v,int w,int c=0){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); }
#define erep(u,i) for(int i=head[u],v=e[i].to,w=e[i].w,c=e[i].c;i;i=e[i].nxt,v=e[i].to,w=e[i].w,c=e[i].c)

int dis[N];
int SPFA(){
	static int inq[N];
	static queue <int> que;
	rep(i,1,V) dis[i]=INF;
	que.push(S),dis[S]=0;
	while(!que.empty()) {
		int u=que.front(); que.pop();
		inq[u]=0;
		erep(u,i) if(w && dis[v]>dis[u]+c) {
			dis[v]=dis[u]+c;
			if(!inq[v]) inq[v]=1,que.push(v);
		}
	}
	return dis[T]<INF;
}
int Dfs(int u,int in) {
	if(u==T) return in;
	int out=0,t=dis[u]; dis[u]=INF;
	erep(u,i) if(w && dis[v]==t+c) {
		int t=Dfs(v,min(in-out,w));
		e[i].w-=t,e[i^1].w+=t,out+=t;
		if(in==out) break;
	}
	if(out) dis[u]=t;
	return out;
}

Pii Dinic(){
	int flow=0,cost=0;
	while(SPFA()) 
		for(int t;(t=Dfs(S,INF));) flow+=t,cost+=dis[T]*t;
	return mp(flow,cost);
}

class CurvyonRails {
	public:
		int getmin(vector <string> field) {
			n=field.size(),m=field[0].size();
			rep(i,0,n-1) rep(j,0,m-1) a[i+1][j+1]=field[i][j];
			k=0,Clear();
			rep(i,1,n) rep(j,1,m) if(a[i][j]!='w') {
				k++;
				rep(d,0,1) id[i][j][d]=++V;
			}
			S=++V,T=++V;
			rep(i,1,n) rep(j,1,m) if(a[i][j]!='w') {
				if((i+j)&1){
					Link(S,++V,2,0);
					rep(d,0,1) {
						Link(V,id[i][j][d],1,0);
						Link(V,id[i][j][d],1,a[i][j]=='C');
						// 如果两条走了同向，就会产生1的代价
					}
					if(i<n && a[i+1][j]!='w') Link(id[i][j][0],id[i+1][j][0],1,0);
					if(j<m && a[i][j+1]!='w') Link(id[i][j][1],id[i][j+1][1],1,0);
				} else {
					Link(++V,T,2,0);
					rep(d,0,1) {
						Link(id[i][j][d],V,1,0);
						Link(id[i][j][d],V,1,a[i][j]=='C');
						// 如果两条走了同向，就会产生1的代价
					}
					if(i<n && a[i+1][j]!='w') Link(id[i+1][j][0],id[i][j][0],1,0);
					if(j<m && a[i][j+1]!='w') Link(id[i][j+1][1],id[i][j][1],1,0);
				}
			}
			Pii ans=Dinic();
			if(ans.first!=k) return -1;
			return ans.second;
		}
};
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!