题目链接：

题意: ...

很容易想到求的是一个最小割=最大流。

之前一直用的刘汝佳的模板STL过题，很久没用过数组模拟了。

再次熟悉一下写法，first数组是索引数组，标记的结点的最后一条边，利用next数组找到上一条边。

1 #include 
     
       2  3 using namespace std; 4  5 #define N 1100000 6 int n,m,first[N],next[N*6],v[N*6],w[N*6],tot,jy,ans,vis[N],S,T,xx,pos[N]; 7  8 void Add(int x,int y,int z) 9 {10     w[tot] = z;11     v[tot] = y;12     next[tot] = first[x];13     first[x] = tot++;14 }15 16 void add(int x,int y,int z)17 {18     Add(x,y,z);19     Add(y,x,z);20 }21 22 bool bfs()23 {24     memset(vis,-1,sizeof(vis)),vis[S]=0;25     queue
      
       q;26     q.push(S);27     while(!q.empty())28     {29         int t=q.front();30         q.pop();31         for(int i=first[t]; ~i; i=next[i])32             if(w[i]&&vis[v[i]]==-1)33                 vis[v[i]]=vis[t]+1,q.push(v[i]);34     }35     return vis[T]!=-1;36 }37 38 int dfs(int x,int y)39 {40     if(x==T)return y;41     int r=0;42     for(int i=first[x]; ~i&&y>r; i=next[i])43         if(w[i]&&vis[v[i]]==vis[x]+1)44         {45             int t=dfs(v[i],min(y-r,w[i]));46             w[i]-=t,w[i^1]+=t,r+=t;47         }48     if(!r)vis[x]=-1;49     return r;50 }51 52 int main()53 {54     memset(first,-1,sizeof(first));55     scanf("%d%d",&n,&m);56     S=m+1,T=n*m+m;57     for(int i=1; i<=n; i++)58         for(int j=1; j