I - I WIN
Time Limit: 2 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87954#problem/I
Description
Given an n × m rectangular tile with each square marked with one of the letters W, I, and N, find the maximal number of triominoes that can be cut from this tile such that the triomino has W and N on the ends and I in the middle (that is, it spells WIN in some order). Of course the only possible triominoes are the one with three squares in a straight line and the L-shaped ones, and the triominoes can't overlap.
Input
First line contains two integers n and m with 1 ≤ m, n ≤ 22. The next n lines contain m characters each (only the letters W, I and N).
Output
Output a single integer: the maximum number of nonoverlapping WIN-triominoes.
Sample Input
4 4
WIIW
NNNN
IINN
WWWI
Sample Output
5
HINT
题意
给你一个n*m的矩形，最多能找出多少不重复的WIN块？
题解：
建图方法：
S-1-W-1-I-1-I-1-N-T
注意点考虑到有一个I可能会与两个不同位置的W,N相连
还有就是模版6666
代码：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//***************************
namespace NetFlow
{
const int MAXN=,MAXM=,inf=1e9;
struct Edge
{
int v,c,f,nx;
Edge() {}
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
void init(int _n)
{
N=_n,sz=; memset(G,-,sizeof(G[])*N);
}
void link(int u,int v,int c)
{
E[sz]=Edge(v,c,,G[u]); G[u]=sz++;
E[sz]=Edge(u,,,G[v]); G[v]=sz++;
}
int ISAP(int S,int T)
{//S -> T
int maxflow=,aug=inf,flag=false,u,v;
for (int i=;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=;
for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false)
{
for (int &it=cur[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+)
{
if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;
pre[v]=u,u=v; flag=true;
if (u==T)
{
for (maxflow+=aug;u!=S;)
{
E[cur[u=pre[u]]].f+=aug;
E[cur[u]^].f-=aug;
}
aug=inf;
}
break;
}
}
if (flag) continue;
int mx=N;
for (int it=G[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[E[it].v]<mx)
{
mx=dis[E[it].v]; cur[u]=it;
}
}
if ((--gap[dis[u]])==) break;
++gap[dis[u]=mx+]; u=pre[u];
}
return maxflow;
}
bool bfs(int S,int T)
{
static int Q[MAXN]; memset(dis,-,sizeof(dis[])*N);
dis[S]=; Q[]=S;
for (int h=,t=,u,v,it;h<t;++h)
{
for (u=Q[h],it=G[u];~it;it=E[it].nx)
{
if (dis[v=E[it].v]==-&&E[it].c>E[it].f)
{
dis[v]=dis[u]+; Q[t++]=v;
}
}
}
return dis[T]!=-;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=,tmp,v;
for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+&&E[it].c>E[it].f)
{
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
{
ret+=tmp; E[it].f+=tmp; E[it^].f-=tmp;
}
}
}
if (!ret) dis[u]=-; return ret;
}
int dinic(int S,int T)
{
int maxflow=,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G[])*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
}
using namespace NetFlow;
char mp[][];
int ss[][]={-,,,,,,,-};
int n,m;
int main()
{
init();
n=read();
m=read();
for(int i=; i<=n; i++)
{
scanf("%s",mp[i]+);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
if(mp[i][j]=='I'){
link((i-)*m+j,(i-)*m+j+,);
}
}
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
if(mp[i][j]=='W')
{
//mpp[n*m+1][(i-1)*m+j]=1;
link(n*m++,(i-)*m+j,);
for(int e=; e<; e++)
if(mp[i+ss[e][]][j+ss[e][]]=='I')
{ link((i-)*m+j,(i+ss[e][]-)*m+j+ss[e][],);
}
}
if(mp[i][j]=='I')
{
for(int e=; e<; e++)
if(mp[i+ss[e][]][j+ss[e][]]=='N')
{
link((i-)*m+j+,(i+ss[e][]-)*m+j+ss[e][],);
}
}
if(mp[i][j]=='N')link((i-)*m+j,n*m++,);
}
}
cout<<dinic(n*m++,n*m+++)<<endl;
return ;
}