Submission #8002355

---

Source Code Expand

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

struct PrimalDual{
    using F=long long;
    static const F INF;
    
    struct Edge{
        int to;
        F cap,cost;
        int rev;
        Edge(int to,F cap,F cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
    };
    
    int n;
    vector<vector<Edge>>G;

    PrimalDual(int n):n(n),G(n){}

    void addEdge(int from,int to,F cap,F cost){
        G[from].push_back(Edge(to,cap,cost,G[to].size()));
        G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
    }


    F minCostFlow(int s,int t,F f){
        F cur=0;

        vector<F>h(n);
        vector<int>prevv(n,-1),preve(n,-1);
        vector<F>dist(n);
        priority_queue<pair<F,int>,vector<pair<F,int>>,greater<pair<F,int>>>que;
            
        while(f>0){
            fill(dist.begin(),dist.end(),INF);
            dist[s]=0;
            que.emplace(0,s); 
            while(que.size()){
                F d;
                int v;
                tie(d,v)=que.top();
                que.pop();
                if(dist[v]<d)continue;
                for(int i=0;i<G[v].size();i++){
                    Edge &e=G[v][i];
                    F nd=dist[v]+e.cost+h[v]-h[e.to];
                    if(e.cap>0&&dist[e.to]>nd){
                        dist[e.to]=nd;
                        prevv[e.to]=v;preve[e.to]=i;
                        que.emplace(nd,e.to);
                    }
                }
            }
            if(dist[t]==INF)return INF;
            for(int v=0;v<n;v++)h[v]+=dist[v];
            F nf=f;
            for(int v=t;v!=s;v=prevv[v]){
                nf=min(nf,G[prevv[v]][preve[v]].cap);
            }
            f-=nf;
            cur+=nf*h[t];
            for(int v=t;v!=s;v=prevv[v]){
                Edge &e=G[prevv[v]][preve[v]];
                e.cap-=nf;
                G[v][e.rev].cap+=nf;
            }
        }
        return cur;
    }
};
const PrimalDual::F PrimalDual::INF=1ll<<50;

signed main(){
    int N,M,D;
    scanf("%lld%lld%lld",&N,&M,&D);
    PrimalDual pd(N+M+D+2);
    int src=N+M+D,snk=N+M+D+1;

    rep(i,M){
        int c,s,k;
        scanf("%lld%lld%lld",&c,&s,&k);
        s--;
        pd.addEdge(N+M+s,N+i,1,0);
        rep(j,k){
            int a;scanf("%lld",&a);
            a--;
            pd.addEdge(N+i,a,1,c);
        }
    }

    rep(i,D){
        int b;scanf("%lld",&b);
        pd.addEdge(src,N+M+i,b,0);
    }

    rep(i,N)pd.addEdge(i,snk,1,0);
    int tmp=pd.minCostFlow(src,snk,N);
    if(tmp==PrimalDual::INF){
        puts("-1");
    }
    else{
        printf("%lld\n",tmp);
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:106:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&N,&M,&D);
                                   ^
./Main.cpp:112:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&c,&s,&k);
                                       ^
./Main.cpp:116:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             int a;scanf("%lld",&a);
                                   ^
./Main.cpp:123:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         int b;scanf("%lld",&b);
                               ^

Judge Result