Battle Over Cities Hard Version

1001 Battle Over Cities - Hard Version

思路：暴力跑每一个点作为被侵略点的情况，求最小生成树即可。

需要注意的情况是，虽然题目说最一开始的时候图是联通的，但是要注意，当一个点被侵略的时候，图可能就不连通了，所以需要判定一下，不连通的情况置为 inf。

// Created by CAD on 2021/5/18.
#include <bits/stdc++.h>
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;

const int maxn=6e6+5;
struct edge{
    int u,v,w;
    bool operator <(edge &e){
        return w<e.w;
    }
}e[maxn];
int f[505];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
int n,m;
vector<pii> ans;
void solve(int x){
    for(int i=1;i<=n;++i)
        f[i]=i;
    int cnt=0,sum=0;
    for(int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(u==x||v==x||find(u)==find(v)) continue;
        cnt++,sum+=w,f[find(u)]=find(v);
    }
    if(cnt<n-2) sum=inf;
    if(ans.empty()) ans.emplace_back(x,sum);
    else {
        if(ans[0].se>sum) return ;
        if(ans[0].se<sum) ans.clear();
        ans.emplace_back(x,sum);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w,t;cin>>u>>v>>w>>t;
        e[i]={u,v,(t==0)?w:0};
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=n;++i)
        solve(i);
    if(ans.empty()||ans[0].se==0) cout<<0<<endl;
    else{
        for(int i=0;i<ans.size();++i){
            cout<<ans[i].fi<<" \n"[i==ans.size()-1];
        }
    }
    return 0;
}