好难好难，将行列当成X和Y，源汇点连接各自的X，Y集，容量为行列的和，相当于从源点流向每一行，然后分配流量给每一列，最后流入汇点，这样执意要推断最后是否满流，就知道有没有解，而解就是每一行流向每一列多少流量。

关键在于怎么推断多解的情况。我想不到啊T_T

题讲解，找到一个长度大于2的环。

想了一想，也就是找到还有剩余流量的环，假设找到了，我就能够把当中一条边的流量转移，由于是一个环，所以它又会达到平衡，不会破坏最大流，可是这样转移后，解就多了一种，所以仅仅要推断是否有一个长度大于2的环就够了。

这里长度为什么要大于2，由于建图时的反向弧会导致 A->B而且B立马->A，这种话，也是一个环，但转移这条环的流量却会破坏最大流。

所以我们在用dfs找环的时候，要注意不能立马走反向弧。

dinic用了当前弧优化。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<string>
#define eps  1e-12
#define INF   0x7fffffff
#define maxn 1005
using namespace std;
int n,m,k;
int en;
int st,ed;
int dis[maxn],cur[maxn];
int que[999999];
struct edge
{
    int to,c,next;
};
edge e[999999];
int head[maxn];
void add(int a,int b,int c)
{
    e[en].to=b;
    e[en].c=c;
    e[en].next=head[a];
    head[a]=en++;
    e[en].to=a;
    e[en].c=0;
    e[en].next=head[b];
    head[b]=en++;
}
int bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[st]=0;
    int front=0,rear=0;
    que[rear++]=st;
    while(front<rear)
    {
        int j=que[front++];
        for(int k=head[j];k!=-1;k=e[k].next)
        {
            int i=e[k].to;
            if(dis[i]==-1&&e[k].c)
            {
                dis[i] = dis[j]+ 1 ;
                que[rear++]=i;
                if(i==ed) return true;
            }
        }
    }
    return false;
}
int dfs(int x,int mx)
{
    if(x==ed || mx==0) return mx;
    int f,flow=0;
    for(int& i=cur[x];i!=-1;i=e[i].next)
    {
        if(dis[x]+1==dis[e[i].to] && (f=dfs(e[i].to,min(mx,e[i].c))))
        {
            e[i].c-=f;
            e[i^1].c+=f;
            flow+=f;
            mx-=f;
            if(!mx)break;
        }
    }
     return flow;
}

void init()
{
    en=0;
    st=0;     //源
    ed=n+m+1;     //汇
    memset(head,-1,sizeof(head));
}
inline int ReadInt()
{
    char ch = getchar();
    int data = http://www.mamicode.com/0;>