4213: 贪吃蛇
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 58 Solved: 24[][][]Description
最近lwher迷上了贪吃蛇游戏，在玩了几天却从未占满全地图的情况下，他不得不承认自己是一个弱菜，只能改去开发一款更弱的贪吃蛇游戏。
在开发的过程中，lwher脑洞大开，搞了一个多条蛇的模式。但由于这种模式太难操作，于是他只好改变游戏的玩法，稍微变化一下游戏目标。
新的游戏是这样的：
一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接)，且只是占据两个格子。蛇与蛇之间不能重叠，蛇也不会与自己重叠。每条蛇还必须满足以下两个条件中的一个：
1、两个端点所在的格子在网格的边界。
2、蛇构成一个环，即两个端点相邻(垂直或水平，不能斜着)，至少要占据4个格子(否则没法形成环)。
给定一个网格，用r x c的字符矩阵描述：‘#’代表障碍物，‘.’代表空地。在满足前面所述的条件下覆盖所有空地，并使得端点在网格边界(即不构成环)的蛇尽量少。（如果一条蛇既构成环，又是端点在边界，那么不计入答案）
例如，以下网格：
可以由下面三种方案覆盖。还有其他的方案，但是没法仅用一条不构成环的蛇就覆盖整个网络的方案。
给定一个网络的描述，输出最少需要多少条不构成环的蛇来覆盖这个网格。如果不存在能够覆盖网格的方案，输出-1。
Input
一个字符矩阵，行数和列数不超过12。输入文件中没有多余的空白字符，每行之后都有换行符。
Output
输出满足题目要求的那个整数。
Sample Input
...... .#.##. .#.... ....#. .##.#. ......
Sample Output
2
HINT
Source
Solution
感觉是插头DP或者费用流...立马把插头DP否了
网格基本上得先黑白染色
感觉环状蛇中每个点一定与两个点相连，非环蛇只有头尾不合两个点相连，所以实际上要算的就是和一个点相连的
S-->白点，容量2 ： 上下界都是2 费用为0
黑点-->T，容量2： 上下界都是2 费用同样为0
表示这个点需要和别的两个点相连
然后白点向四周黑点扩展出一条边 容量为1 费用为0
这样就是环状蛇的建图（显然环蛇不计入答案，所以费用全部置成0）
然后特判边界情况，边界上的白点-->T 费用1 容量1 表示非环蛇的情况
然后跑上下界最小费用流，ans/2即为答案，因为非环蛇的头尾都被累计，相当于1条蛇贡献2，所以除二即可
上下界最小费用流？理论什么的忘记了。。。
实现起来就是用超级源汇替代原来的源汇，再由次级汇连次级源INF，然后跑超级源汇之间的费用流
无解按照特有判定，S出来的边应该全都满流，否则无解
Code
#include#include #include #include #include #include using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}#define MAXM 100010#define MAXN 10010int N,M,cas;#define mN 15#define mM 15char G[mN][mM];struct EdgeNode{ int next,to,cap,cost;}edge[MAXM];int head[MAXN],cnt=1;inline void AddEdge(int u,int v,int w,int c) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w; edge[cnt].cost=c;}inline void InsertEdge(int u,int v,int w,int c) {AddEdge(u,v,w,c); AddEdge(v,u,0,-c);}int dis[MAXN],S,T,s,t,MinCost; bool mark[MAXN];#define INF 0x7fffffffbool spfa(){ queue q; memset(mark,0,sizeof(mark)); for (int i=S; i<=T; i++) dis[i]=INF; q.push(T); dis[T]=0; mark[T]=1; while (!q.empty()) { int now=q.front(); q.pop(); mark[now]=0; for (int i=head[now]; i; i=edge[i].next) if (edge[i^1].cap && dis[edge[i].to]>dis[now]+edge[i^1].cost) { dis[edge[i].to]=dis[now]+edge[i^1].cost; if (!mark[edge[i].to]) q.push(edge[i].to),mark[edge[i].to]=1; } } return dis[S]!=INF;}int dfs(int loc,int low){ mark[loc]=1; if (loc==T) return low; int w,used=0; for (int i=head[loc]; i; i=edge[i].next) if (edge[i].cap && !mark[edge[i].to] && dis[edge[i].to]==dis[loc]-edge[i].cost) { w=dfs(edge[i].to,min(low-used,edge[i].cap)); edge[i].cap-=w; edge[i^1].cap+=w; used+=w; MinCost+=w*edge[i].cost; if (used==low) return low; } return used;}int zkw(){ int tmp=0; while (spfa()) { mark[T]=1; while (mark[T]) memset(mark,0,sizeof(mark)),tmp+=dfs(S,INF); } return tmp;}bool Judge() { bool f=1; for (int i=head[S]; i; i=edge[i].next) if (edge[i].cap) {f=0;break;} return !f;}inline bool Check(int x,int y) { if (x>=1 && x<=N && y>=1 && y<=M && G[x][y]!='#') return 1; return 0;}int D[mN*mM],id[mN][mM],col[mN][mM];void BuildGraph(){ S=0; T=N*M+3; s=N*M+1; t=N*M+2; int idd=0; for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) id[i][j]=++idd,col[i][j]=(i+j)&1; for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) if (col[i][j]) if (Check(i,j)) D[s]-=2,D[id[i][j]]+=2; else; else if (Check(i,j)) D[id[i][j]]-=2,D[t]+=2; else; for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) if (col[i][j] && Check(i,j)) { if (Check(i-1,j)) InsertEdge(id[i][j],id[i-1][j],1,0); if (Check(i,j-1)) InsertEdge(id[i][j],id[i][j-1],1,0); if (Check(i+1,j)) InsertEdge(id[i][j],id[i+1][j],1,0); if (Check(i,j+1)) InsertEdge(id[i][j],id[i][j+1],1,0); } for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) if (i==1 || i==N || j==1 || j==M) if (col[i][j]) if (Check(i,j)) InsertEdge(id[i][j],t,1,1); else; else if (Check(i,j)) InsertEdge(s,id[i][j],1,1); else; for (int i=1; i<=t; i++) if (D[i]>0) InsertEdge(S,i,D[i],0); else if (D[i]<0) InsertEdge(i,T,-D[i],0); InsertEdge(t,s,INF,0);}int tp;int main(){ tp=1; while (scanf("%s",G[tp]+1)!=EOF) tp++; N=tp-1,M=strlen(G[1]+1); BuildGraph(); zkw(); if (Judge()) {puts("-1"); return 0;} printf("%d\n",MinCost>>1); return 0;}
什么垃圾读入方式，恶心！