求助,dinic wa22分
查看原帖
求助,dinic wa22分
151647
sycqwq楼主2022/1/27 23:38

rt

#include<bits/stdc++.h>
#define inf INT_MAX
using namespace std;
const int maxn=1005,maxm=1000005;
int tot=1,de[maxn],a[maxn],b[maxn],head[maxn],n,s,t,m,tp,ans;
struct node
{
    int u,v,nxt,w;
}e[maxm<<1];
void add(int x,int y,int w)
{
    e[++tot].u=x;
    e[tot].v=y;
    e[tot].w=w;
    e[tot].nxt=head[x];
    head[x]=tot;
}
int bfs()
{
    memset(de,0,sizeof de);
    queue<int> q;
    q.push(s);
    de[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(!de[v]&&e[i].w)
            {
                de[v]=de[x]+1;
                q.push(v);
            }
        }
    }
    // for(int i=1;50;i++)
    //     cout<<de[i]i<=<<' ';
    // getchar();
    return de[t];
}
int dfs(int u,int x)
{
    if(u==t)
        return x;
    int s=0;
    for(int i=head[u];i&&x;i=e[i].nxt)
    {
        int v=e[i].v; 
        // getchar();
        if(de[v]==de[u]+1&&e[i].w>0)
        {
        // cout<<u<<' '<<v<<' '<<de[u]<<' '<<de[v]<<endl;
            int res=dfs(v,min(x,e[i].w));
            // cout<<res<<endl;
            e[i].w-=res;
            e[i^1].w+=res;
            x-=res;
            s+=res;
        }
    }
    if(!s)
        de[u]=0;
    return s;
}
int main()
{
    cin>>n;
    s=n+1;
    t=n+2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        tp+=a[i];
        add(s,i,a[i]);
        add(i,s,0);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        tp+=b[i];
        add(i,t,b[i]);
        add(t,i,0);
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int k,c1,c2;
        cin>>k>>c1>>c2;
        add(s,n+2+i,c1);
        add(n+2+i,s,0);
        add(n+2+i+m,t,c2);
        add(t,n+2+i+m,0);
        tp+=c1+c2;
        for(int j=1;j<=k;j++)
        {
            int x;
            cin>>x;
            add(n+2+i,x,inf);
            add(x,n+2+i,0);
            add(x,n+2+m+i,inf); 
            add(n+2+m+i,x,0);
        }
    }
    while(bfs())    
    {
        ans+=dfs(s,inf);
    }
    cout<<tp-ans<<endl;
    return 0;
}
2022/1/27 23:38
加载中...