QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#674768#9102. Zayin and Elementsucup-team5071#ML 0ms3640kbC++203.2kb2024-10-25 17:24:442024-10-25 17:24:44

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 17:24:44]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3640kb
  • [2024-10-25 17:24:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=205,M=3005;
struct SSP{
    int cnt=1,hd[N],nxt[M<<1],to[M<<1],limit[M<<1],cst[M<<1];
    void init(){
        memset(hd,0,sizeof(hd));
        cnt=1;
    }
    int add(int u,int v,int w,int c){
        //cout<<u<<" "<<v<<" "<<w<<" "<<c<<endl;
        nxt[++cnt]=hd[u],hd[u]=cnt,to[cnt]=v,limit[cnt]=w,cst[cnt]=c;
        nxt[++cnt]=hd[v],hd[v]=cnt,to[cnt]=u,limit[cnt]=0,cst[cnt]=-c;
        return cnt-1;
    }
    int fr[N],fl[N],in[N],dis[N];
    pair<int,int> min_cost(int s,int t){
        int flow=0,cost=0;
        while(true){
            queue<int> q;
            memset(dis,0x3f,sizeof(dis));
            memset(in,0,sizeof(in));
            fl[s]=1e9,dis[s]=0,q.push(s);
            while(!q.empty()){
                int cur=q.front();
                q.pop();in[cur]=0;
                for(int i=hd[cur];i;i=nxt[i]){
                    int it=to[i],d=dis[cur]+cst[i];
                    // cout<<"i="<<i<<" it="<<it<<endl;
                    if(limit[i]&&d<dis[it]){
                        fl[it]=min(limit[i],fl[cur]),fr[it]=i,dis[it]=d;
                        if(!in[it])in[it]=1,q.push(it);
                    }
                }
            }
            if(dis[t]>1e9)return {flow,cost};
            flow+=fl[t],cost+=dis[t]*fl[t];
            for(int u=t;u!=s;u=to[fr[u]^1])limit[fr[u]]-=fl[t],limit[fr[u]^1]+=fl[t];
        }
    }
}sol;
void Solve(){   
    int n,m;
    cin>>n>>m;
    int all=0;
    sol.init();
    int s=0,t=n+m+1;
    int res=0;
    for(int i=1;i<=n;i++)
    sol.add(m+i,t,1,0);
    vector<int> outb(m+1);
    for(int i=1;i<=m;i++){
        int a,b,c,siz;
        cin>>a>>b>>c>>siz;
        sol.add(s,i,a,0);
        outb[i]=sol.add(s,i,b*2,1);
        sol.add(s,i,c,2);
        all+=b*2+c*2;
        for(int j=1;j<=siz;j++){
            int x;
            cin>>x;
            sol.add(i,m+x,1,0);
        }
    }
    auto [flow,cost]=sol.min_cost(s,t);
    if(flow<n){
        cout<<"-1\n";return;
    }
    for(int i=1;i<=m;i++)if(sol.limit[outb[i]]%2){
        vector<int> st(n+m+1);
        function<int(int)>dfs = [&](int x){
            if(x==i)return 0;
            
            if(x<=m&&sol.limit[outb[x]]%2){
                sol.limit[outb[x]]--;
                return 1;
            }
            for(int j=sol.hd[x];j;j=sol.nxt[j])if(sol.to[j]>=1&&sol.to[j]<=n+m&&sol.limit[j]){
                if(!st[sol.to[j]]&&dfs(sol.to[j])){
                    st[sol.to[j]]=1;
                    sol.limit[j]--;
                    sol.limit[j^1]++;
                    return 1;
                }
            }
            return 0;
        };
        int flag=0;
        for(int j=sol.hd[i];j;j=sol.nxt[j])if(sol.to[j]>m&&sol.to[j]<=n+m&&sol.limit[j]){
             if(!st[sol.to[j]]&&dfs(sol.to[j])){
                st[sol.to[j]]=1;
                sol.limit[j]--;
                sol.limit[j^1]++;
                flag=1;
                sol.limit[outb[i]]++;
                break;
            }
        }
        cost+=flag;
    }
    cout<<(all-cost)/2<<"\n";
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T;
    cin>>T;
    while(T--)Solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

input:

2
5
2
2 3 1 2 3 1
1 1 1 3 4 5 2
5
2
2 3 1 1 3
1 0 1 2 1 2

output:

5
-1

result:

ok 2 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

5
9
10
0 0 10 2 3 8
0 0 10 2 4 6
0 8 2 2 2 4
0 0 10 3 1 3 8
0 4 6 2 2 3
0 8 2 3 2 6 7
0 9 1 2 1 7
0 2 8 3 1 4 9
0 7 3 1 5
0 0 10 3 5 6 9
3
10
0 9 1 1 2
0 5 5 1 1
0 1 9 1 1
0 7 3 1 1
0 7 3 0
0 0 10 0
0 6 4 1 3
0 9 1 0
0 7 3 0
0 9 1 1 2
90
20
0 6 4 12 1 4 5 22 32 64 66 67 73 87 88 89
0 1 9 12 3 8 21 3...

output:


result: