結果

問題 No.748 yuki国のお財布事情
ユーザー kafuka97kafuka97
提出日時 2019-08-24 11:36:58
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 4,308 bytes
コンパイル時間 1,673 ms
コンパイル使用メモリ 175,212 KB
実行使用メモリ 15,996 KB
最終ジャッジ日時 2023-08-03 17:57:12
合計ジャッジ時間 3,745 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 8 ms
4,844 KB
testcase_14 AC 14 ms
5,644 KB
testcase_15 AC 10 ms
4,992 KB
testcase_16 AC 27 ms
7,660 KB
testcase_17 AC 56 ms
12,880 KB
testcase_18 AC 68 ms
14,724 KB
testcase_19 AC 72 ms
15,996 KB
testcase_20 AC 64 ms
14,436 KB
testcase_21 AC 67 ms
15,016 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 46 ms
11,828 KB
testcase_26 AC 69 ms
15,660 KB
testcase_27 AC 68 ms
15,724 KB
testcase_28 AC 48 ms
11,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef int64_t i64;
typedef uint64_t ui64;

class djset{
private:
    int sz;
    int *par;
public:
    djset(int n){
        sz=n;
        par=new int[sz];
        for(int i=0;i<sz;i++) par[i]=1;
    }
    int find(int x){
        return par[x]<=0?-(par[x]=-find(-par[x])):x;
    }
    void unite(int x,int y){
        int px=find(x),py=find(y);
        if(px==py) return;
        if(par[px]<par[py]){
            int tmp=px;
            px=py;
            py=tmp;
        }
        par[px]+=par[py];
        par[py]=-px;
    }
    bool same(int x,int y){
        return (find(x)==find(y));
    }
    int size(int x){
        return par[find(x)];
    }
    int group(void){
        int cnt=0;
        for(int i=0;i<sz;i++){
            if(par[i]>0) cnt++;
        }
        return cnt;
    }
    void refr(void){
        delete[] par;
    }
};

class graph{
private:
    struct vrtx{
        int to;
        int64_t cost;
    };
    struct adj{
        int start;
        int to;
        int64_t cost;
    };
    int nd;
    int edg;
    std::vector<vrtx> *node;
    std::vector<adj> edge;
public:
    graph(int n,int m){
        nd=n;
        edg=m;
        node=new std::vector<vrtx>[nd];
    }
    void add_dir(int s,int t,int64_t c){
        node[s].push_back({t,c});
        edge.push_back({s,t,c});
    }
    void add_undir(int s,int t,int64_t c){
        node[s].push_back({t,c});
        node[t].push_back({s,c});
        edge.push_back({s,t,c});
    }
    void dlt_dir(int s,int t){
        for(int i=0;i<node[s].size();i++){
            if(node[s][i].to==t){
                node[s].erase(node[s].begin()+i);
                break;
            }
        }
    }
    void dlt_undir(int s,int t){
        for(int i=0;i<node[s].size();i++){
            if(node[s][i].to==t){
                node[s].erase(node[s].begin()+i);
                break;
            }
        }
        for(int i=0;i<node[t].size();i++){
            if(node[t][i].to==s){
                node[t].erase(node[t].begin()+i);
                break;
            }
        }
    }
    void refr(void){
        for(int i=0;i<nd;i++) std::vector<vrtx>().swap(node[i]);
        delete[] node;
        std::vector<adj>().swap(edge);
    }
    bool islnk(void);
    void dfs(int r,int64_t **p,bool **vst);  // 木, (*p)[], vst[] を呼び出す前に初期化
    bool ispls(void);
    void bellford(int s,int64_t **d);
    void dijkstra(int s,int64_t **d);  // 負の閉路なし
    void bfs(int s,int64_t **d);  // 辺に重み無し or 木
    void waflo(bool isdir,int64_t ***d);
    int64_t minstw_dir(int r);  // class: djset, class: skewheap が必要
    int64_t minstw_undir(void);  // class: djset が必要
    void edmonds(int r,std::vector<std::pair<int,int>> &p);  // class: djset, class: skewheap が必要
    void kruscal(std::vector<std::pair<int,int>> &p);  // class: djset が必要
    void prim(std::vector<std::pair<int,int>> &p);
    void cumulsum(int s,int64_t **d);  // 木
    void cumulprd(int s,int64_t **d);  // 木
};

int64_t graph::minstw_undir(void){
    adj *es=new adj[edg];
    for(int i=0;i<edg;i++) es[i]={edge[i].start,edge[i].to,edge[i].cost};
    std::sort(es,es+edg,[](const adj &e1,const adj &e2){return e1.cost<e2.cost;});
    djset uf(nd);
    int64_t res=0;
    for(int i=0;i<edg;i++){
        if(!uf.same(es[i].start,es[i].to)){
            uf.unite(es[i].start,es[i].to);
            res+=es[i].cost;
        }
    }
    return res;
}

int main(void){
    int n,m,k;
    scanf("%i%i%i",&n,&m,&k);
    graph g(n,m);
    int *a=new int[m],*b=new int[m];
    i64 *c=new i64[m];
    int *e=new int[k];
    i64 sum=0;
    for(int i=0;i<m;i++){
        scanf("%i%i%lli",&a[i],&b[i],&c[i]);
        a[i]--;
        b[i]--;
        sum+=c[i];
    }
    if(k==0){
        for(int i=0;i<m;i++) g.add_undir(a[i],b[i],c[i]);
        printf("%lli\n",sum-g.minstw_undir());
        return 0;
    }
    for(int i=0;i<k;i++){
        scanf("%i",&e[i]);
        e[i]--;
    }
    int j=0;
    i64 need=0;
    for(int i=0;i<m;i++){
        if(i!=e[j]) g.add_undir(a[i],b[i],c[i]);
        else{
            need+=c[i];
            g.add_undir(a[i],b[i],0);
            j++;
        }
    }
    printf("%lli\n",sum-g.minstw_undir()-need);
    return 0;
}
0