题解 UVA1537 【Picnic Planning】

· · 题解

更好的阅读

发篇带有较为严谨证明的题解

我们不妨设Park为1号点。将边按边权从小到大排序，考虑选出的边要满足什么条件：

  1. 选出的边构成原图的一个生成树

  2. 1$号点度数不超过$k

答案就是选边权之和最小的边集，满足上述条件

证明：

遗传性：显然

交换性：假设两个边集S,T，其中|S|<|T|，且T中任意一条边加入S都不能形成独立集，那么T中每条边的端点一定在S中的同一联通块上。对于一个S中的联通块G的边集A，设T中满足两端都在G中的边集为B，由于T也是独立集，所以|B| \leq |G|-1 = |A|。不难归纳出|T| \leq |S|，与假设矛盾

证明：

遗传性：显然

交换性：假设两个边集S,T，其中|S|<|T|，且T中任意一条边加入S都不能形成独立集。若S中与1相连的边数小于k，则任意一条不在S的边加入都形成独立集，|T| \leq |S|，与假设矛盾；否则S中与1相连的边数为k，则任意一条不在S且不与1相连的边加入都形成独立集，设T中与1相邻的边数为a,(0 \leq a \leq k)，则|T|-a \leq |S| -k，即|T| \leq |S| -k +a \leq |S|，与假设矛盾

那么满足题意的合法边集就是两个拟阵的交，求拟阵交即可，时间复杂度为O(Tnm^2)


//μ's forever
#include <bits/stdc++.h>
#define M 905
#define ll long long
using namespace std;
int T,n,m,xp[M],yp[M],wp[M],x[M],y[M],w[M],pk,k;
map<string,int> mp;
pair<int,int> ar[M];
int s,t,val[M],fa[M],pre[M];
vector<int> g[M];
bool usd[M],ins[M];
ll dis[M],ans;
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
bool merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return 0;
    fa[x]=y;return 1;
}
bool chk1(bool usd[]){
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i) if(usd[i]) 
    if(!merge(x[i],y[i])) return 0;
    return 1;
}
bool chk2(bool usd[]){
    int ct=0;
    for(int i=1;i<=m;++i)
        if(usd[i]&&(x[i]==pk||y[i]==pk))
            ++ct;
    return ct<=k;
}
void spfa(){
    for(int i=1;i<=t;++i) dis[i]=1e18;
    queue<int> q;dis[s]=0,q.push(s),ins[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop(),ins[u]=0;
        for(int i=0;i<(int)g[u].size();++i){
            int v=g[u][i];
            if(dis[v]>dis[u]+val[v]){
                dis[v]=dis[u]+val[v],pre[v]=u;
                if(!ins[v]) ins[v]=1,q.push(v);
            }
        }
    }
}
void matroid_inter(){
    memset(usd,0,sizeof(usd));s=m+1,t=m+2;
    while(1){
        for(int i=1;i<=t;++i) g[i].clear();
        for(int i=1;i<=t;++i) if(usd[i]) val[i]=-w[i]; else val[i]=w[i];
        for(int i=1;i<=m;++i){ if(!usd[i]) continue;
            for(int j=1;j<=m;++j){ if(usd[j]) continue;
                usd[i]=0,usd[j]=1;
                if(chk1(usd)) g[i].push_back(j);
                if(chk2(usd)) g[j].push_back(i);
                usd[i]=1,usd[j]=0;
            }
        }
        for(int i=1;i<=m;++i){ if(usd[i]) continue;
            usd[i]=1;
            if(chk1(usd)) g[s].push_back(i);
            if(chk2(usd)) g[i].push_back(t);
            usd[i]=0;
        }
        spfa();
        if(dis[t]>1e15) break;
        for(int i=pre[t];i!=s;i=pre[i])
            usd[i]^=1;
    }
}
int main()
{
    cin>>T;
    while(T--){
        mp.clear();ans=n=0;
        cin>>m;
        for(int i=1;i<=m;++i){
            string a,b;
            cin>>a>>b>>wp[i];
            ar[i]=make_pair(wp[i],i);
            if(mp.find(a)!=mp.end()) xp[i]=mp[a];
            else{ mp[a]=++n,xp[i]=n; if(a=="Park") pk=n;}
            if(mp.find(b)!=mp.end()) yp[i]=mp[b];
            else{ mp[b]=++n,yp[i]=n; if(b=="Park") pk=n;}
        }
        sort(ar+1,ar+1+m);
        for(int i=1;i<=m;++i)
            x[i]=xp[ar[i].second],y[i]=yp[ar[i].second],w[i]=wp[ar[i].second];
        cin>>k;
        matroid_inter();
        for(int i=1;i<=m;++i) if(usd[i]) ans+=w[i];
        cout<<"Total miles driven: "<<ans<<endl;
        if(T) puts("");
    }
    return 0;
}