11分求调
查看原帖
11分求调
681351
Tobiichi_Origami楼主2023/10/17 09:22
#include<bits/stdc++.h>
using namespace std;
const int N=510,M=1e5+10;
const int Inf=0x3f3f3f3f;
struct edge{
    int to,next,w;
}ed[M<<1];
int he[N],tot=-1;
int d[N],cur[N];
int n,m,s,t,sum;
void insert(int u,int v,int w){
    tot++;
    ed[tot].to=v;
    ed[tot].w=w;
    ed[tot].next=he[u];
    he[u]=tot;
}
bool bfs()
{
    memset(d,-1,sizeof(d));
    queue<int>q;
    d[s]=0;cur[s]=he[s];
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=he[u];i!=-1;i=ed[i].next)
        {
            int v=ed[i].to;
            if(d[v]==-1&&ed[i].w)
            {
                d[v]=d[u]+1;
                cur[v]=he[v];
                if(v==t) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
int dfs(int u,int lim)
{
    if(u==t) return lim;
    int flow=0;
    for(int i=cur[u];i!=-1&&flow<lim;i=ed[i].next)
    {
        int v=ed[i].to;
        cur[u]=i;
        if(d[v]==d[u]+1&&ed[i].w)
        {
            int t=dfs(v,min(ed[i].w,lim-flow));
            if(!t) d[v]=-1;
            ed[i].w-=t;ed[i^1].w+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int res=0,flow;
    while(bfs())
        while(flow=dfs(s,Inf))
            res+=flow;
    return res;
}
int main()
{
    memset(he,-1,sizeof(he));
    scanf("%d %d",&m,&n);
    s=0,t=n+m+1;
    for(int i=1;i<=m;i++){
        int w;
        scanf("%d",&w);
        sum+=w;
        insert(s,i,w),insert(i,s,0);
        char tools[10000];
        memset(tools,0,sizeof tools);
        cin.getline(tools,10000);
        int ulen=0,tool;
        while (sscanf(tools+ulen,"%d",&tool)==1)
        {
            insert(i,tool+m,Inf),insert(tool+m,i,Inf);
            if (tool==0) 
                ulen++;
            else {
                while (tool) {
                    tool/=10;
                    ulen++;
                }
            }
            ulen++;
        }
    }
    for(int i=1;i<=n;i++){
        int w;
        scanf("%d",&w);
        insert(i+m,t,w),insert(t,i+m,0);
    }
    int res=dinic();
    for(int i=1;i<=m;i++)
        if(d[i]!=-1) printf("%d ",i);
    printf("\n");
    for(int i=1;i<=n;i++)
        if(d[i+m]!=-1) printf("%d ",i);
    printf("\n");
    printf("%d",sum-res);
    return 0;
}
2023/10/17 09:22
加载中...