社区讨论
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 条回复,欢迎继续交流。
正在加载回复...