ISAP网络流

ISAP是的dicnic基础上优化得到的一直最大流算法，其包含了当前弧优化和分层图优化，且分层图无需重新构建，会在运行过程中处理。

ISAP 的终止条件为出现断层div。
对于层数 > div 的点，满流。
反之，则未满流。

在最大全闭合图问题中，答案为满流的点的组合。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int _ = 2e4+10;
const int N = 410,inf=0x3f3f3f3f;

void in(int &x){
    x=0;int y = 1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    x*=y;
}
void o(int x){
    printf("%lld",x);
}

int n,m;
//前向星村边，注意始边从2开始，而不再是1。
struct {int v,nxt,f;}e[_];int cnt = 1;
struct ISAP{
//规定起点和重点,一般为n+1，和n+2
    int S = 0,T=0;
//    head 前线星头部，初始化为0
    int head[N]={0};
//    d 当前弧线 gap 各层点的数量 h 点的高度
    int h[N],gap[N],d[N];
    void add(int u,int v,int f){
//       正边，反边。
        e[++cnt]={v,head[u],f};head[u]=cnt;
        swap(u,v);
        e[++cnt]={v,head[u],0};head[u]=cnt;
    }
    int sap(int u,int flow){
//        流至T，退出
        if(u==T)return flow;
//        流量
        int rec=0;
//        从当前弧搜索可行流
        for(int i=d[u];i;i=e[i].nxt){
            if(h[u]==h[e[i].v]+1&&e[i].f){
//              流量 ret
                int ret = sap(e[i].v,min(flow-rec,e[i].f));
//              正流+，反流减小并且记录当前弧
                e[i].f-=ret;e[i^1].f+=ret;d[u]=i;
//               达到可行最大流即使终止，
                if((rec+=ret)==flow)return flow;
            }
        }
//        当前层数点数-1，若出现断层则已经找到最大流
        if(!(--gap[h[u]]))h[S]=T;
//        下一层++，当前弧线还原
        gap[++h[u]]++;d[u]=head[u];
        return rec;
    }
    void init(){
        S=n+1,T=n+2;
        for(int i=1;i<=T;i++)head[i]=d[i]=0,h[i]=gap[i]=0;
    }
    int cal(){
        for(int u=0,v=0,i=1;;i++){
            in(u);in(v);
            if(u==-1)break;
            add(u,v,1);
        }
        for(int i=1;i<=m;i++)add(S,i,1);
        for(int i=m+1;i<=n;i++)add(i,T,1);
        int maxflow;
        gap[maxflow=0]=T;
        for(int i=1;i<=T;i++)d[i]=head[i];
        while(h[S]<T)maxflow+=sap(S,inf);
        return maxflow;
    }
    void printedge(){
        for(int i=1;i<=n;i++){
            for(int j=head[i];j;j=e[j].nxt){
                if(j%2==0&&e[j].f==0&&e[j].v!=S&&e[j].v!=T){
                    o(i);putchar(' ');o(e[j].v);putchar('
');
                }
            }
        }
    }
}MAXF;

signed main(){
//    in(n);in(m);
    in(m);in(n);
    
    o(MAXF.cal());putchar('
');
    MAXF.printedge();
    return 0;
}