USACO 2018 Dec Gold

A. Fine Dining

对于这种从很多点走到同一个终点的问题，很容易想到从终点倒着走到各点的处理方式，于是我们先从 $n$ 开始做一遍 dijkstra，得到从 $n$ 到各点 $i$ 的最短距离 $dis[i]$。

然后考虑一头牛什么时候可以吃到干草，对于某头牛 $i$，若存在一个干草堆 $j$，使得 $n$ 到 $i$ 的最短距离与 $n$ 到 $j$ 的最短距离加上 $j$ 到 $i$ 的最短距离的差值小于 $j$ 的美味值，则牛 $i$ 可以吃到干草，更直观一点，设 $j$ 到 $i$ 的最短距离为 $ld$ 的话，当存在 $j$ 满足

$$dis[j]+ld-dis[i]\le y[i]$$

时，牛 $i$ 能吃到干草。

我们发现我们不知道的就只有 $ld$ 了，于是我们要算 $ld$，暴力的做法可以直接对每个干草堆跑一遍 dijkstra，但是这样做肯定会超时，于是有一个很妙的想法，建一个虚拟点，将它与这些干草堆相连，再去跑一遍最短路就可以，需要思考的是虚拟点与干草堆连的边的边权，假设从虚拟点出发到其他某个点 $i$ 的最短距离为 $dis2[i]$ 则 $dis2[i]$ 的构成就是某个干草堆 $j$ 到 $i$ 的最短距离 $ld$ 加上虚拟点到这个干草堆的边权，再观察一下之前写的不等式，我们将其变形一下，得到：

$$dis[i]\ge dis[j]-y[j]+ld$$

所以我们将边权设为 $dis[j]-y[j]$ 的话，就会很自然而且方便比较，所以我们就设其为 $dis[j]-y[j]$，然后题就做完了。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;

const int N=5e4+5,M=1e5+5,inf=1e9;
int n,m,k;
int e[M<<1],ne[M<<1],w[M<<1],h[N],idx;
int dis[N],lim[N];
bool vis[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

void dijkstra(int u)
{
    for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
    dis[u]=0;
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    heap.push({dis[u],u});
    while(heap.size()){
        pii t=heap.top();
        heap.pop();
        int u=t.y;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i],ww=w[i];
            if(dis[v]>dis[u]+ww){
                dis[v]=dis[u]+ww;
                heap.push({dis[v],v});
            }
        }
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>k;
    for(int i=1,a,b,c;i<=m;i++){
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dijkstra(n);
    for(int i=1;i<n;i++) lim[i]=dis[i];
    for(int i=1,p,y;i<=k;i++){
        cin>>p>>y;
        add(n+1,p,dis[p]-y);
    }
    dijkstra(n+1);
    for(int i=1;i<n;i++){
        if(lim[i]>=dis[i]) cout<<"1\n";
        else cout<<"0\n";
    }

    return 0;
}

B. Cowpatibility

比较集合的相似度时，我们常常会用到容斥原理，这道题就是这样。

直接算不和谐的对数不好算，于是我们考虑先统计至少有一种相同口味的奶牛对数，最后用总奶牛对数减去它。

对于每头奶牛，枚举它喜欢的 5 种口味的所有非空子集，设当前枚举的口味子集为 $S$，之前有 $f[S]$ 头奶牛都包含这个子集，那么当前奶牛可以与这 $f[S]$ 头奶牛组成奶牛对。

根据容斥原理：

• 当子集大小为奇数时，加上 $f[S]$；
• 当子集大小为偶数时，减去 $f[S]$。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<unordered_map>
using namespace std;
typedef long long ll;

int n;
ll ans;
string s[5];
unordered_map<string,ll> f;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=0;j<5;j++) cin>>s[j];
        sort(s,s+5);
        string t;
        for(int S=1;S<(1<<5);S++){
            t="";
            int cnt=0;
            for(int j=0;j<5;j++){
                if((S>>j)&1){
                    cnt++;
                    t=t+" "+s[j];
                }
            }
            if(cnt&1) ans+=f[t];
            else ans-=f[t];
            f[t]++;
        }
    }
    cout<<(ll)n*(ll)(n-1)/2-ans<<"\n";

    return 0;
}