7-266畅通工程之局部最小花费问题（35分）

#include 
#define inf 0x3f3f3f3f
#define MAX 1e9;
#define FRE() freopen("in.txt","r",stdin)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 200;
int mp[maxn][maxn],w[maxn],vis[maxn];
int N;

void init() {
    for(int i = 1; i<=N; i++) {
        for(int j = 1; j<=N; j++) {
            mp[i][j] = inf;
        }
    }
    int st,en,co,state,k = N*(N-1)/2;
    for(int i = 0; i) {
        scanf("%d%d%d%d",&st,&en,&co,&state);
        if(state == 0) {
            mp[st][en] = co;
            mp[en][st] = co;
        } else {
            mp[st][en] = 0;
            mp[en][st] = 0;
        }
    }
}

void prim() {
    for(int i = 1; i<=N; i++){//从1顶点出开始生成最小生成树
        vis[i] = 0;
        if(i != 1)
            w[i] = mp[1][i];
    }
    vis[1] = 1;
    int pos = 0,MIN = inf;
    for(int i = 0; i) {
        MIN = inf,pos = 0;
        for(int j = 1; j<=N; j++) {//从没有访问过的顶点中找到下一个距离最短的边
            if(vis[j] == 0 && MIN>w[j]) {
                MIN = w[j];
                pos = j;
            }
        }
        vis[pos] = 1;
        for(int j = 1; j<=N; j++) {//用这个最小的顶点的邻接边的权值更新w[]的值
            if(!vis[j] && mp[pos][j]<w[j]) {
                w[j] = mp[pos][j];
            }
        }
    }
}

void check1() {
    for(int i = 1; i<=N; i++) {
        for(int j = 1; j<=N; j++) {
            printf("%d ", mp[i][j]);
        }
        printf("\n");
    }
}

void check2() {
    for(int i = 1; i<=N; i++) {
        printf("%d ",w[i]);
    }
    printf("\n");
}

int main() {
    //FRE();
    scanf("%d",&N);
    init();
    prim();
    //check2();
    int sum = 0;
    for(int i = 1; i<=N; i++) {
        sum += w[i];
    }
    printf("%d\n",sum);
    return 0;
}
/*
PutIn:
4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0
PutOut:
3
*/

#include 
#define inf 0x3f3f3f3f
#define MAX 1e9;
#define FRE() freopen("in.txt","r",stdin)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 5000;
int vis[maxn],pre[maxn];
int N;
struct edge{
    int st,en,co;
}e[maxn];

void init() {
    memset(vis,0,sizeof(vis));
    for(int i = 1; i<=N; i++){//注意pre数组的初始化
        pre[i] = i;
    }
    int st,en,co,state,k = N*(N-1)/2;
    for(int i = 0; i) {
        scanf("%d%d%d%d",&st,&en,&co,&state);
        e[i].st = st;
        e[i].en = en;
        if(state){
            e[i].co = 0;
        }else{
            e[i].co = co;
        }
    }
}

int Find(int x){//查找x点的祖先
    return pre[x]==x ? x : pre[x] = Find(pre[x]);
}

bool cmd(edge a,edge b){
    return a.co<b.co;
}

void solve(){
    int ans = 0,cnt = 0,k = N*(N-1)/2;
    for(int i = 0; i){
        edge te = e[i];
        int tx = Find(te.st),ty = Find(te.en);
        if(tx!=ty){//如果两个点不在同一个集合中,就通过并查集将两个点放在一个集合中
            cnt++;
            ans += te.co;
            pre[tx] = ty;
        }
        if(cnt==N-1)//当确定的边数到达规定的数量的时候，就推出循环
            break;
    }
    //printf("cnt:%d\n",cnt);
    printf("%d\n",ans);
}

void check(){
    int k = N*(N-1)/2;
    for(int i = 0; i){
        printf("%d ",e[i].co);
    }
    printf("\n");
}

int main() {
    //FRE();
    scanf("%d",&N);
    init();
    int k = (N-1)*N/2;
    sort(e,e+k,cmd);//将所有的边的权值按从小到大进行排序
    //check();
    solve();
    return 0;
}
/*
PutIn:
4
1 2 1 1
1 3 4 0
1 4 1 1
2 3 3 0
2 4 2 1
3 4 5 0
PutOut:
3
*/