rt

萌新刚学网络流，菜菜，求大佬捞捞

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e3+5;
const int M=1e5+5;
const int INF=0x3f3f3f3f;
struct Edge{
    int u,v,w,c,next;
}edge[M<<1],eedge[M<<1];
int n,tot=1,s,t,ans=0,ret=0;
int head[N],cur[N],d[N],vis[N],used[M],mp[N][N],g[N][N];
inline void add(int u,int v,int w,int c){
    edge[++tot]=(Edge){u,v,w,c,head[u]},head[u]=tot;eedge[tot]=edge[tot];
    edge[++tot]=(Edge){v,u,0,-c,head[v]},head[v]=tot;eedge[tot]=edge[tot];
}
inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') {f=-1;} ch=getchar();}
    while(isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
    return s*f;
}
inline void write(int x){
    int top=0,sta[35];
    while(x) {sta[top++]=x%10,x/=10;}
    while(top) {putchar(sta[--top]+'0');}
}
inline int SPFA()
{
    queue <int> q;
    memset(d,0x3f,sizeof(d));
    memcpy(cur,head,sizeof(head));
    q.push(s),d[s]=0;vis[s]=1;
    while (!q.empty())
    {
        int u=q.front();
        vis[u]=0;q.pop();
        for (int i=head[u];i;i=edge[i].next)
        {
            if (used[i]) continue;
            int v=edge[i].v;
            if (d[v]>d[u]+edge[i].c && edge[i].w)
            {
                d[v]=d[u]+edge[i].c;
                if (!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return d[t]==INF?0:1;
}
inline int Dinic(int u,int f)
{
    if (u==t) return f;
    vis[u]=1;int k,res=0;
    for (int i=cur[u];i && f;i=edge[i].next)
    {
        int v=edge[i].v;cur[u]=i;
        if (used[i]) continue;
        if (d[v]==d[u]+edge[i].c && !vis[v] && edge[i].w)
        {
            k=Dinic(v,min(edge[i].w,f));
            if (!k) {d[v]=INF;continue;}
            edge[i].w-=k,edge[i^1].w+=k;
            res+=k,f-=k;ret+=edge[i].c*k;
        }
    }
    vis[u]=0;
    return res;
}
int main()
{
    n=read();s=0,t=n*2+1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            mp[i][j]=read();
    }
    for (int i=1;i<=n;i++)
    {
        add(s,i,1,0);
        add(i+n,t,1,0);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            add(i,j+n,1,-mp[i][j]);
    } 
    while (SPFA()) ans+=Dinic(s,INF);
    int tmp=ret;
    for (int i=2;i<=tot;i+=2)
    {
        if (!edge[i].w)
        {
            ret=ans=0;
            used[i]=1,used[i^1]=1;
            memcpy(edge,eedge,sizeof(eedge));
            while (SPFA()) ans+=Dinic(s,INF);
            if (ret>tmp)
                g[edge[i].u][edge[i].v]=1;
            used[i]=0,used[i^1]=0;
        }
    }
    printf("%d\n",-tmp);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            if (g[i][j+n]) 
                printf("%d %d\n",i,j);
    }
    return 0;
}