题意：给定一个网格，有一些格子是障碍不用管，剩余的是空地，你要用一些起点和终点在边界上的路径或环来完全覆盖掉空地，如果使用第一种，会付出1的代价，求最小代价，不能覆盖则输出-1。
现在看到网格而且数据范围小的基本上的是网络流黑白染色啊。。（废话你在做网络流的题啊）
其实这道题和之前那个只用环覆盖的很像，只不过这里可以用路径。之前我们考虑的是每个点都会被贯穿，也就说度数会是2，所以当初那道题我们用的是二分图跑费用流，但这里有路径，怎么办？
首先图的基本关系很简单，相邻点之间连普通的容量1，费用0就好了。然后我们考虑强制要让每个点被贯穿，黑白染色后，用下限去限制，S向黑点连下限为2的边，白点向T连下限为2的边。问题来了，有的方案是有路径的，路径的端点并没有被贯穿，这怎么整？
巧妙之处来了。对于端点，我们现在的问题是多了流量，怎么办？把它直接导去就完了。也就是说，我们对于边界上的黑点，向T连一条无下限，上限为1，费用为1的边，白色同理。为什么巧妙呢，这不但解决了端点度数为1的问题，而且一旦出现这种情况，就说明出现了路径，对答案产生贡献，我们再加上费用来记录，跑最小费用可行流就完了。答案记得除2，因为头尾算了两次。判断有无解看有无可行流就好了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 inline int read(){ 4 int x=0,f=1; char a=getchar(); 5 while(a<'0' || a>'9') {if(a=='-') f=-1; a=getchar();} 6 while(a>='0' && a<='9') x=x*10+a-'0',a=getchar(); 7 return x*f; 8 } 9 #define INF 1e9 10 #define N 505 11 #define in ini 12 #define id(i,j) (((i)-1)*m+(j)) 13 const int dir[4][2]={0,1,0,-1,1,0,-1,0}; 14 int ans,n,m,head[N],cnt,d[N],a[N],p[N],S,SS,T,TT,TOT,in[N]; 15 char st[25][25]; 16 bool vis[N]; 17 queue<int>q; 18 struct edges{ 19 int fr,to,cap,flow,cost,next; 20 }e[2*N]; 21 22 inline void insert(int u,int v,int f,int c){ 23 e[cnt]=(edges){u,v,f,0,c,head[u]};head[u]=cnt++; 24 e[cnt]=(edges){v,u,0,0,-c,head[v]};head[v]=cnt++; 25 } 26 inline bool spfa(){ 27 memset(d,0x3f,sizeof(d)); 28 d[S]=0; a[S]=INF; q.push(S); 29 while(!q.empty()){ 30 int x=q.front(); q.pop(); vis[x]=0; 31 for(int i=head[x];i>=0;i=e[i].next) 32 if(d[e[i].to]>d[x]+e[i].cost && e[i].flow<e[i].cap){ 33 d[e[i].to]=d[x]+e[i].cost; p[e[i].to]=i; 34 a[e[i].to]=min(a[x],e[i].cap-e[i].flow); 35 if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to); 36 } 37 } 38 return d[T]<INF; 39 } 40 inline void mincf(){ 41 ans+=a[T]*d[T]; TOT-=a[T]; 42 int u=T; 43 while(u!=S){ 44 e[p[u]].flow+=a[T]; 45 e[p[u]^1].flow-=a[T]; 46 u=e[p[u]].fr; 47 } 48 } 49 int main(){ 50 memset(head,-1,sizeof(head)); 51 while(scanf("%s",st[++n]+1)!=EOF); n--; 52 m=strlen(st[1]+1); 53 SS=0; TT=n*m+1; S=TT+1; T=TT+2; 54 for(int i=1;i<=n;i++) 55 for(int j=1;j<=m;j++){ 56 if(st[i][j]=='#') continue; 57 if((i+j)&1){ 58 if(i==1 || i==n || j==1 || j==m) insert(SS,id(i,j),1,1); 59 in[TT]+=2; in[id(i,j)]-=2; 60 }else{ 61 if(i==1 || i==n || j==1 || j==m) insert(id(i,j),TT,1,1); 62 in[SS]-=2; in[id(i,j)]+=2; 63 for(int k=0;k<4;k++){ 64 int tx=i+dir[k][0],ty=j+dir[k][1]; 65 if(tx<1 || tx>n || ty<1 || ty>m || st[tx][ty]=='#') continue; 66 insert(id(i,j),id(tx,ty),1,0); 67 } 68 } 69 } 70 insert(TT,SS,INF,0); 71 for(int i=SS;i<=TT;i++){ 72 if(in[i]>0) insert(S,i,in[i],0),TOT+=in[i]; 73 if(in[i]<0) insert(i,T,-in[i],0); 74 } 75 while(spfa()) mincf(); 76 if(!TOT) printf("%d ",ans/2); 77 else puts("-1"); 78 return 0; 79 }