結果

問題 No.1316 Maximum Minimum Spanning Tree
ユーザー rqoi031
提出日時 2025-05-27 16:36:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 2,825 bytes
コンパイル時間 1,279 ms
コンパイル使用メモリ 109,056 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-27 16:36:09
合計ジャッジ時間 4,170 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 78
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:80:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   80 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:82:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |         scanf("%d%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2],&edge[i][3]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
#include<array>
#include<tuple>
typedef long long ll;
constexpr ll inf{1000000000000000000},lim{2000000000};
constexpr int N{50},M{200};
template<int N,int M>
struct flow {
    int n,s,t;
    struct edge {
        int v;
        ll w;
        int next;
    };
    edge e[(M<<1)+5];
    int en,last[N+5];
    void initialize(const int &n,const int &s,const int &t) {
        this->n=n,this->s=s,this->t=t;
        std::fill(last+1,last+n+1,0),en=1;
    }
    inline void add_edge(const int &u,const int &v,const ll &w) {
        e[++en]={v,w,last[u]},last[u]=en;
        e[++en]={u,0,last[v]},last[v]=en;
    }
    int dis[N+5],que[N+5];
    bool bfs() {
        std::fill(dis+1,dis+n+1,-1);
        int qb{1},qe{1};
        dis[t]=0,que[1]=t;
        while(qb<=qe) {
            int &u{que[qb++]};
            if(u==s) {
                return true;
            }
            for(int i=last[u];i;i=e[i].next) {
                int &v{e[i].v};
                if(e[i^1].w!=0&&dis[v]==-1) {
                    dis[v]=dis[u]+1,que[++qe]=v;
                }
            }
        }
        return false;
    }
    int lst[N+5];
    ll dfs(const int &u,const ll &f) {
        if(u==t) {
            return f;
        }
        ll d{0};
        for(int &i=lst[u];i;i=e[i].next) {
            int &v{e[i].v};
            if(e[i].w!=0&&dis[u]==dis[v]+1) {
                ll s{dfs(v,std::min(e[i].w,f-d))};
                e[i].w-=s,e[i^1].w+=s,d+=s;
                if(d==f) {
                    return d;
                }
            }
        }
        return d;
    }
    ll dinic() {
        ll res{0};
        while(bfs()) {
            std::copy(last+1,last+n+1,lst+1);
            res+=dfs(s,inf);
        }
        return res;
    }
};
flow<N+2,N+M*2> G;
std::array<int,4> edge[M+5];
int val[M+5];
int main() {
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2],&edge[i][3]);
    }
    std::sort(edge+1,edge+m+1,[&](const auto &x,const auto &y)->bool {
        return x[2]<y[2];
    });
    ll ans0{0},ans1{0};
    for(int i=1;i<=m;i++) {
        G.initialize(n+2,n+1,n+2);
        for(int j=1;j<=n;j++) {
            G.add_edge(j,G.t,k);
        }
        G.add_edge(G.s,edge[i][0],inf);
        G.add_edge(G.s,edge[i][1],inf);
        ll sum{-k};
        for(int j=1;j<i;j++) {
            sum-=val[j];
            G.add_edge(G.s,edge[j][0],val[j]);
            G.add_edge(edge[j][0],edge[j][1],val[j]);
        }
        sum+=G.dinic();
        val[i]=std::min<ll>(sum,edge[i][3]);
        ans0+=val[i],ans1+=ll(val[i])*edge[i][2];
    }
    if(ans0<ll(k)*(n-1)) {
        return puts("-1"),0;
    }
    printf("%lld\n",ans1);
    return 0;
}
0