P8095 [USACO22JAN] Cereal 2 S 题解

· · 题解

现在连银组都有蓝题了吗？

思路：

求奶牛的最优排列，不难想在这道题要用到二分图匹配。匹配过程与板子大体相同，只不过加多了一个 second。

匹配好以后，剩下的也不难了。

算法流程：

  1. 二分图匹配，求出一种最优解。对于每一箱麦片，得到它应该被哪头牛吃（或者没被吃），可以使结果最优。

  2. 对牛的顺序进行约束，设某头牛编号为 x，它的第一喜欢、第二喜欢的麦片编号分别为 a，b，如果牛 x 吃到的是麦片 b，那麦片 a 肯定早就被吃了，此时吃掉麦片 a 的牛 y 一定要排在牛 x 之前，对于这种情况，建一条从 x 到 y 的单向边，表示 x 排在 y 之后。

  3. 进行拓扑排序，输出答案。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)){if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}
    return f * x;
}

int vis[N], n, m, ans;
int fri[N], sec[N], to[N], ind[N];
vector<int> e[N];
inline void add(int x, int y)
{
    e[x].push_back(y);
    ind[y]++;
}

inline bool dfs(int u)//二分图匹配板子
{
    if(!vis[fri[u]])
    {
        vis[fri[u]] = 1;
        if ((!to[fri[u]]) || dfs(to[fri[u]]))
        {
            to[fri[u]] = u;
            vis[fri[u]] = 0;
            return 1;
        }
        vis[fri[u]] = 0;
    }
    if(!vis[sec[u]])
    {
        vis[sec[u]] = 1;
        if((!to[sec[u]]) || dfs(to[sec[u]]))
        {
            to[sec[u]] = u;
            vis[sec[u]] = 0;
            return 1;
        }
        vis[sec[u]] = 0;
    }
    return 0;
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)
    {
        fri[i] = read();
        sec[i] = read();
    }
    for (int i = 1; i <= n; i++)
    {
        if(dfs(i))
        {
            ans++;
        }
    }
    memset(vis, 0, sizeof(vis));
    printf("%d\n", n-ans);
    for(int i = 1; i <= m; i++)
    {
        if(i == sec[to[i]])//第 i 个麦片被编号为 to[i] 的牛所吃
        {
            add(to[fri[to[i]]],to[i]);
        }
    }
    int head = 0;
    while(head < n)
    {
        for(int i = 1; i <= n; i++)
        {
            if(vis[i])
                continue;
            if(!ind[i])
            {
                vis[i] = 1;
                printf("%d\n", i);
                head++;
                int l = e[i].size();
                for (int j = 0; j < l; j++)
                {
                    int too = e[i][j];
                    ind[too]--;
                }
            }
        }
    }
}