社区讨论

11分

P2762太空飞行计划问题参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi6i3xjb
此快照首次捕获于
2025/11/20 05:15
4 个月前
此快照最后确认于
2025/11/20 05:15
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define inf 2147483647
#define min(x,y) ((x)<(y)?(x):(y))
    struct node{int x,y,c,next,other;} a[40001];
    int last[201];
    int n,m,len=0,sum=0,ans=0,st,ed;
    bool bz[201];
    char c[10010];
void ins(int x,int y,int c)
{
    a[++len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;a[len].other=len+1;
    a[++len].x=y;a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;a[len].other=len-1;
}
int f[40001],h[201];
bool bfs()
{
    int head=1,tail=2;
    memset(h,0,sizeof(h));
    h[st]=1;
    f[1]=st;
    while(head<tail)
    {
        int x=f[head];
        for(int i=last[x];i!=-1;i=a[i].next)
        {
            int y=a[i].y;
            if(a[i].c>0&&h[y]==0)
            {
                h[y]=h[x]+1;
                f[tail++]=y;
                bz[y]=true;
            }
        }
        head++;
    }
    if(h[ed]>0) return true; else return false;
}
int dfs(int x,int f)
{
    int s=0,t;
    if(x==ed) return f;
    for(int i=last[x];i!=-1;i=a[i].next)
    {
        int y=a[i].y;
        if(a[i].c>0&&h[y]==h[x]+1&&f>s)
        {
            s+=(t=(dfs(y,min(f-s,a[i].c))));
            a[i].c-=t;
            a[a[i].other].c+=t;
        }
    }
    if(s==0) h[x]=0;
    return s;
}
int dinic()
{
    while(bfs())
        ans+=dfs(st,inf);
    return ans;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout); 
    memset(last,-1,sizeof(last));
    scanf("%d %d",&n,&m);
    st=0,ed=n+m+1;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        sum+=x;
        ins(st,i,x);
        char ch=getchar();
        while(((ch=getchar())>='0')&&ch<='9')
        {
            int t=ch-48;
            while(((ch=getchar())>='0')&&ch<='9')
                t=t*10+ch-48;
            ins(i,t+n,inf);
            if(ch=='\n') break;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        ins(i+n,ed,x);
    }
    ans=dinic();
    for(int i=1;i<=n;i++)
        if(bz[i]) printf("%d ",i);
    printf("\n");
    for(int i=1;i<=m;i++)
        if(bz[i+n]) printf("%d ",i);
    printf("\n%d",sum-ans);
}

回复

5 条回复,欢迎继续交流。

正在加载回复...