题解 P2798 【爆弹虐场 】

· · 题解

本题也可采取图论做法，相当于是双边权情况下的最小生成树。

因为题目保证t<T,所以边权取T的边不可能超过k条（超过的拿t替换更优）。

这样我们只要在克鲁斯卡尔的时候前k条边用T扩展，后n-1-k条用t即可，记录最大边权。

#include<cstdio>
#include<queue>
using namespace std;
struct edge{
    int u,v,t,T;
}e;
struct cmp1{bool operator () (edge a,edge b) {return a.t>b.t;} };
struct cmp2{bool operator () (edge a,edge b) {return a.T>b.T;} };
priority_queue<edge,vector<edge>,cmp1> q1;
priority_queue<edge,vector<edge>,cmp2> q2;
int fa[10005];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
int max(int x,int y) {return x>y?x:y;}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int j=1;j<=m;j++)
    {
        scanf("%d%d%d%d",&e.u,&e.v,&e.T,&e.t);
        q1.push(e);q2.push(e);
    }
    m=0;int ans=0;
    while(q2.size()&&m<k)
    {
        e=q2.top();q2.pop();
        int x=find(e.u),y=find(e.v);
        if(x==y) continue;
        ans=max(ans,e.T);
        m++;
        fa[x]=y;
    }
    while(q1.size()&&m<n-1)
    {
        e=q1.top();q1.pop();
        int x=find(e.u),y=find(e.v);
        if(x==y) continue;
        ans=max(ans,e.t);
        m++;
        fa[x]=y;
    }
    printf("%d\n",ans);
    return 0;
}