题解 P2999 【[USACO10NOV]巧克力牛奶Chocolate Milk】

· · 题解

蒟蒻lolte的题解

这题不难想到要用到拓扑排序，但我不像其他两位题解一样需要平均分配。

我用拓扑关系来递推每个点到牛奶流量。挤奶机为1，其余为 from 的流量之和。

特别的，当一个点的出度大于1时，这个点后面的点绝不是混合器，即非答案。

当一个点的流量为牛奶总流量时，这个点是答案。

代码如下

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch<='9'&&ch>='0') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int maxn=100010;
int n,id[maxn],od[maxn],to[maxn],q[maxn],liu[maxn],l=1,r=0,tot=0;
bool ji[maxn];
int main(){
    memset(id,0,sizeof(id));
    memset(od,0,sizeof(od));
    n=read();
    for (int i=1;i<n;++i) {
        int a,b;
        a=read();
        b=read();
        to[a]=b;
        ++od[a];//出度+1 
        ++id[b];//入度+1 
    }
    for (int i=1;i<=n;++i) {
        if (!id[i]) {
            q[++r]=i;//加入队列 
            liu[i]=1;//挤奶器流量为1 
            ++tot;//统计牛奶总流量 
            ji[i]=1;//标记为挤奶器 
        }
    }
    while (l<=r) {
        //拓扑流程 
        int u=q[l];
        if (od[u]>1) {
            //入度>1，后面直接不管 
            liu[to[u]]=0;
            ++l;
            continue;
        }
        liu[to[u]]+=liu[u];//累加流量 
        --id[to[u]];
        if (!id[to[u]]) {//加点 
            q[++r]=to[u];
        }
        ++l;
    }
    r=0;
    for (int i=1;i<=n;++i) {
        if (ji[i]) continue;//挤奶器不管 
        if (liu[i]==tot) q[++r]=i;//统计答案 
    }
    for (int i=1;i<=r;++i) printf("%d\n",q[i]);
}

_ (:з」∠) ---