第二问求所有二分图最大权完美匹配中都出现的边

大概就是，跑完第一遍费用流后找有流量的边，然后枚举删去每一条并重新跑费用流

根据题解写了两种

一种是

int main(){
    n=read();s=n*3+1;t=s+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            val[i][j]=read();
            add(i,j+n,1,-val[i][j]);
            add(j+n,i,0,val[i][j]);
            id[i][j]=tot;
        }
    for(int i=1;i<=n;i++){
        add(s,i,1,0);add(i,s,0,0);
        add(i+n,t,1,0);add(t,i+n,0,0);
    }
    dinic();printf("%d\n",-res);
    int fir=res;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!e[id[i][j]].dis) id[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(!id[i][j]) continue;
            nf=id[i][j],nt=id[i][j]^1;res=0;
            for(int k=1;k<=tot;k++) e[k]=E[k];
            dinic();
            if(res>fir){printf("%d %d\n",i,j);break;}
        }
    return 0;
}

另一种是

int main(){
    n=read();s=n*3+1;t=s+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            val[i][j]=read();
            add(i,j+n,1,-val[i][j]);
        }
    int cut=tot;
    for(int i=1;i<=n;i++)
        add(s,i,1,0),add(i+n,t,1,0);
    dinic();printf("%d\n",-res);
    int fir=res;
    for(int i=2;i<=cut;i+=2) if(!e[i].dis) flag[i]=1;
    for(int i=2;i<=cut;i+=2)
        if(flag[i]){
            res=0;
            d[i]=1;d[i^1]=1;memcpy(e,E,sizeof E);
            dinic();if(res>fir) id[e[i].fr][e[i].to]=1;
            d[i]=0;d[i^1]=0;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(id[i][j+n]){
                printf("%d %d\n",i,j);
                break;
            }
        }
    return 0;
}

可以看出两种代码在输出方案的部分都有共同点

就是能保证输出的每行第一个数互不相等并且单调递增

但是有个点 WA 了以后都给出这样的信息

wrong answer On line 3 column 1, read 1, expected 4.

不知道为什么第三行也就是第二次输出 $i$ 会是 $1$

在线等