T6 女装大佬 题解

· · 个人记录

受 执念WHY dalao的邀请来验个题（雾）

听说只能用爆搜？不信邪的我要来了一句话题意：

从一个n×n的矩阵中选m个数，不能有两个数在同一行或同一列，求他们和的最大值

看着这句话，我陷入了沉思

不能在同一行同一列？那不就是……二分图最大权独立集吗=-=

（给萌新做这种东西确实不太友好了）

T62430 女装大佬

题目难度：\color{blue}\text{提高+/省选-} ~ \color{purple}\text{省选/NOI-}

算法：\text{KM}完美匹配\text{/zkw}费用流+基础建模

建议代码长度：1k~2k

建议用时：20\text{min}（精通以上算法）/40\text{min}（会以上算法但不精通）/15\text{min}（不会以上算法）

该篇解析算法：费用流

注意点：由于我给出题人的是 \text{zkw}费用流 的题解，所以出题人的数据是把 \text{EK} 卡掉的，使用 \text{EK} 并不能 \text{AC}

解析：

首先发现行列不能重复，考虑在行列间连边，可以保证每一行和每一列都最多被使用一次。

说详细一点就是建立一个二分图，左侧点为行编号（从1到n），右侧点为列编号（从n+1到n\times 2），然后在中间连边。

此时我们得到了一张图，但是这些边上的信息都还没有填。

我们知道，费用流的边除去一般的起点终点，无非就是容量和费用，于是我们分别考虑。

首先，由于一对行列最多被使用一次，所以容量毫无疑问是1，而费用也很显然，就是给出矩阵中的a[i][j]。

此时我们解决了建图的一半问题，剩下的一半问题就是超级源和超级汇如何连了。

我们知道，求解一个费用流的题目，源点和汇点是必不可少的，但是在求解二分图最大权独立集时，明显没有给出源点和汇点，此时我们就需要自己建立源点和汇点了。

于是我们建立一个超级源点和一个超级汇点，从超级源点向每个行连一条容量为1的边，代表每一行最多被使用一次，再从每个列向超级汇点连一条容量为1的边，代表每一列最多被使用一次。

此时我们如果直接跑最大费用最大流，可以通过样例2，但是样例1会输出一个比样例大的答案，为什么呢？

此时此刻，回想这道题的题面，我们似乎还有一个参数没有用上——m。

最多选m个人，意味着我们需要再一次限制流量，也就是限制总流量最大为m。

这时我们有两种做法，一是在跑费用流时，流量到达m直接退出，另一种就不用劳神去修改函数了，我们建立一个“终极源点”，连向超级源点，容量为m，这样我们就可以限制流量为m了。

（我在求解本题的时候使用了取负费用的做法，所以最后输出的是最小费用的相反数，跑的也是最小费用最大流）

代码：

（\text{SS}为一开始的超级源点，\text{S}为“终极源点”）

#include<bits/stdc++.h>
#define inf 1010580540
using namespace std;
deque <int> q;
int cnt=1,fst[5005],nxt[1000005],to[1000005],w[1000005],cot[1000005],cur[5005];
int n,m,S,T,dis[5005],maxflow,mincost;
bool inq[5005],vis[5005];
void AddEdge(int u,int v,int c,int fl)
{
    to[++cnt]=v;
    nxt[cnt]=fst[u];
    fst[u]=cnt;
    w[cnt]=c;
    cot[cnt]=fl;
}
bool Spfa()
{
    memset(dis,60,sizeof(dis));
    memset(inq,0,sizeof(inq));
    q.push_front(T);
    dis[T]=0;
    inq[T]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=fst[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]-cot[i] && w[i^1])
            {
                dis[v]=dis[u]-cot[i];
                if(!inq[v])
                {
                    if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                }
            }
        }
    }
    return dis[S]!=inf;
}
int Dfs(int u,int flow)
{
    vis[u]=1;
    if(u==T || !flow) return flow;
    int used=0;
    for(int i=cur[u];i;i=nxt[i])
    {
        cur[u]=i;
        int v=to[i];
        if(dis[v]==dis[u]-cot[i] && w[i] && !vis[v])
        {
            int fl=Dfs(v,min(flow,w[i]));
            if(fl)
            {
                used+=fl;
                flow-=fl;
                w[i]-=fl;
                w[i^1]+=fl;
                if(!flow) break;
            }
        }
    }
    return used;
}
void zkwMCMF()
{
    while(Spfa())
    {
        vis[T]=1;
        while(vis[T])
        {
            memcpy(cur,fst,sizeof(fst));
            memset(vis,0,sizeof(vis));
            int fl=Dfs(S,inf);
            maxflow+=fl;
            mincost+=dis[S]*fl;
        }
    }
}
int main()
{
    int SS;
    scanf("%d %d",&n,&m);
    S=0;
    T=n*2+1;
    SS=n*2+2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            AddEdge(i,j+n,1,-x);
            AddEdge(j+n,i,0,x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        AddEdge(SS,i,1,0);
        AddEdge(i,SS,0,0);
        AddEdge(i+n,T,1,0);
        AddEdge(T,i+n,0,0);
    }
    AddEdge(S,SS,m,0);
    AddEdge(SS,S,0,0);
    zkwMCMF();
    printf("%d\n",-mincost);
    return 0;
}