兔
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
小粉兔用集训队的奖金买下了一片地。

这片地上有 n 个房子，有些房子之间有道路，有些房子之间则是杂草。

她可以花费一定的代价拆毁一条道路，或是啃光一片草使得两个房子间可以通行（大雾）。

她喜欢生成树，所以她要让所有道路形成一棵生成树。

求最小花费。
输入
第一行一个数，n。

接下来 n 行，每行 n 个数，代表 ai,j。如果为正数，说明它们之间没有道路，需要 ai,j的花费来修建；如果为负数，说明它们之间有道路，需要 −ai,j的花费来拆毁。
输出
一行一个数，代表最小花费。
样例输入 Copy
3
0 1 -3
1 0 5
-3 5 0
样例输出 Copy
1
提示
对于 100% 的数据，5≤n≤1000,1≤|ai,j(i≠j)|≤1000，保证所有 ai,i=0且 ai,j=aj,i 。

题意：
给定一张已经存在部分边的图，可以删边，也可以建边，两者都需要费用。求生成树的最小花费。
思路：
因为删边也是需要费用的，所以删边后再建边的策略性劣于直接建边。
我们可以直接在原图上建边，这样的花费是最小的。
再来考虑一下什么时候删边，根据生成树的定义，如果构成环的话，就必须删掉部分边。
可以遍历一遍点，如果遍历到这个边时，边的两个端点已经连通，我们就可以直接删除这条边，在这个过程中，需要按照边的权值从大到小排序，因为如果删边肯定是要删后面的边的可能性大，为了减少花费，就优先选择权值小的边。
所以总结一下就是：先在原图上进行删边和合并的操作，这时的权值是按照从大到小排序的，如果不加边就可以构成生成树，直接输出即可。否则，就要再跑一遍 kruskal算法。
要注意！！记录边的数组要开的大一点0.0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1100,maxm=1e6+7;

ll n;
ll g[maxn][maxn];
struct node{
    ll a,b,w;
    bool flag;
}A[maxm];
ll cnt=0;
ll res=0;
bool flag=0;
ll root[maxn];

bool cmp_max(node a,node b){
    return a.w>b.w;
}

bool cmp_min(node a,node b){
    return a.w<b.w;
}

ll Find(ll x){
    return x==root[x]?x:root[x]=Find(root[x]);
}

void kruskal1(){
    for(ll i=1;i<=n;i++) root[i]=i;
    sort(A+1,A+1+cnt,cmp_max);
    ll tot=0;
    for(int i=1;i<=cnt;i++)
        if(A[i].flag){ ///有路
            ll x=A[i].a,y=A[i].b,w=A[i].w;
            x=Find(x),y=Find(y);
            if(x!=y){
                tot++;
                root[x]=y;
            }
            else res+=w;
        }
    if(tot==n-1) flag=1;
}

ll kruskal2(){
    sort(A+1,A+1+cnt,cmp_min);
    for(ll i=1;i<=cnt;i++)
        if(!A[i].flag){
            ll x=A[i].a,y=A[i].b,w=A[i].w;
            x=Find(x),y=Find(y);
            if(x!=y){
                res+=w;
                root[x]=y;
            }
        }
    return res;
}

void AC(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=n;j++)
            scanf("%lld",&g[i][j]);
    for(ll i=1;i<=n;i++)
        for(ll j=i+1;j<=n;j++){
            if(g[i][j]<0){
              ///  A[++cnt]={i,j,-g[i][j],1};///有路
                cnt++;
                A[cnt].a=i;A[cnt].b=j;
                A[cnt].w=-g[i][j];
                A[cnt].flag=1;
            }

            else{
                ///A[++cnt]={i,j,g[i][j],0};///没有路
                cnt++;
                A[cnt].a=i;A[cnt].b=j;
                A[cnt].w=g[i][j];
                A[cnt].flag=0;
            }

        }
    if(flag) printf("%lld",res);
    else printf("%lld\n",kruskal2());
}

int main(){
    AC();
    return 0;
}