[USACO21FEB] Minimizing Edges P

· · 题解

题目描述

点此看题

这道题基本不涉及任何算法，但是思维难度极高。

网上没有这道题的题解，我的思路是从官方题解那里学来的，希望能帮到你。

解法

首先讲一讲为什么我考试的时候会暴毙掉，因为我觉得最优解的构造是和原图紧密相关的，所以我在原树上搞，然后就凉了。因为这道题的提问方式是构造一个新图，没有人告诉你一定要在原图上面改，所以在适当的时候一定要抛弃原图。

首先可以求出数组 a[i][0/1] 表示到 i 的奇数最短路和偶数最短路，不难发现因为可以反复经过最近的一条边，所以两个图相等当且当且仅当跑出来的 a 数组相等，a 数组可以很容易 O(n) 直接 \tt bfs 求出。

求出原图的 a 数组之后就不要管原图了，设 h(i)=(\min(a[i][0/1]),\max(a[i][0/1])) 就表示按大小排的奇偶路径二元组，首先如果原图是二分图那么特判掉，答案是 n-1（因为二分图的情况 a[i][0/1] 有一个没有意义，所以特判），然后我们来考虑点 i 合法的时候满足什么条件，点 1 太特殊了，所以我们暂时不考虑它，设 h(i)=(x,y)：

再来多解释下上面的结论，首先为什么情况这么唯一呢？因为 \tt tly 巨佬告诉我们了一个三角形不等式(?)，也就是有边相连的点的最短路只会绝对值之差小于等于 1，那么就只用讨论 x-1,x,x+1 这些情况，然后为了保证第一维小于等于第二维所以才讨论一下分出第二种情况和第三种情况。

现在考虑怎么用这个结论来做题吧，我们把 (x,y) 相同的点分到一起，然后你发现情况 2/3 的 x+y 和一定，所以可以把 x+y 一定的点划分成一层，同一层的按 x 排序，这样 h(j) 就是连向以前层的，h(j_1) 是连向同层但是是之前的点，还是分情况来讨论，设 S(x,y) 表示 h(i)=(x,y) 这类点的点数，那么有这样几种情况：

下面就直接用贪心做了，因为第一种情况只用连一条边，而二三种情况可能会连两条边，依据这个为主要思想贪心即可。

具体实现就写一个 \tt map 即可，还有就是上面都没有考虑 1 这个特殊的点，如果 1 有自环的话那么需要特判，直接输出 n 即可。然后就耐性地讨论吧，时间复杂度 O(n\log n)

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define pii pair<int,int>
#define make make_pair 
const int M = 200005;
const int inf = 1e9;
int read()
{
    int x=0,f=1;char c;
    while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
    while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
int T,n,m,k,ans,tot,f[M],a[M][2];
map<pii,int> mp,cnt;
struct edge
{
    int v,next;
    edge(int V=0,int N=0) : v(V) , next(N) {}
}e[2*M];
struct node
{
    int x,y;
    bool operator < (const node &b) const
    {
        if(x+y!=b.x+b.y) return x+y<b.x+b.y;
        return x<b.x;
    }
}b[M];
void bfs()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<=1;j++)
            a[i][j]=inf;
    queue<int> q;
    q.push(1);a[1][0]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=f[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(a[u][0]<inf && a[v][1]==inf)
            {
                a[v][1]=a[u][0]+1;
                q.push(v);
            }
            if(a[u][1]<inf && a[v][0]==inf)
            {
                a[v][0]=a[u][1]+1;
                q.push(v);
            }
        }
    }
}
void solve()
{
    bfs();
    if(a[1][1]==1)//1有自环
    {
        printf("%d\n",n);
        return ;
    }
    for(int i=1;i<=n;i++)//是二分图 
        if(a[i][0]==inf || a[i][1]==inf)
        {
            printf("%d\n",n-1);
            return ;
        }
    for(int i=1;i<=n;i++)//把每个点分类 
    {
        pii t=make(a[i][0],a[i][1]);
        if(t.first>t.second) swap(t.first,t.second);
        mp[t]++;
        if(mp[t]==1)//加到数组上面排序
            b[++k]=node{t.first,t.second};
    }
    sort(b+1,b+1+k);
    for(int i=1;i<=k;i++)
    {
        int x=b[i].x,y=b[i].y;
        pii t=make(x,y),t3=make(x+1,y-1);
        pii t1=make(x-1,y-1),t2=make(x-1,y+1);
        if(mp[t1]>0 && mp[t2]==0)
            ans+=mp[t];//直接连上去
        if(mp[t1]==0 && mp[t2]>0)
        {
            ans+=max(0,mp[t]-cnt[t]);//补连向j1的边
            if(x+1==y)//是第三种情况
                ans+=(mp[t]+1)/2;//上取整 
            else
            {
                ans+=mp[t];//连到(x+1,y-1)去
                cnt[t3]+=mp[t]; 
            }
        }
        if(mp[t1]>0 && mp[t2]>0)
        {
            if(mp[t]>cnt[t])
                ans+=mp[t]-cnt[t];//连(x-1,y-1)
            cnt[t]=min(cnt[t],mp[t]);//别忘了写这个 
            if(x+1==y)
                ans+=(cnt[t]+1)/2;
            else
            {
                ans+=cnt[t];
                cnt[t3]+=cnt[t];
            }
        }
    }
    printf("%d\n",ans);
}
int main()
{
    //freopen("minimizing.in","r",stdin);
    //freopen("minimizing.out","w",stdout);
    T=read();
    while(T--)
    {
        mp.clear();
        cnt.clear();
        n=read();m=read();
        tot=1;k=0;ans=0;
        for(int i=1;i<=n;i++)
            f[i]=0;
        for(int i=1;i<=m;i++)
        {
            int u=read(),v=read();
            e[++tot]=edge(v,f[u]),f[u]=tot;
            e[++tot]=edge(u,f[v]),f[v]=tot;
        }
        solve();
    }
}