社区讨论
迷之11分,求助
P2762太空飞行计划问题参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6o1ntc
- 此快照首次捕获于
- 2025/11/20 08:01 4 个月前
- 此快照最后确认于
- 2025/11/20 08:01 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define MAXN 100+10
using namespace std;
const int INF=1<<29;
int ans=0;
inline int read(){
int out=0;
char c=getchar();
while(c<48||c>57) c=getchar();
while(c<=57&&c>=48){
out=(out<<1)+(out<<3)+c-48;
c=getchar();
}
return out;
}
inline void write(int x){
if(x>9) write(x/10);
putchar(x%10+48);
}
inline int min(int a,int b){return a<b?a:b;}
struct Edge{int u,v,cap,flow;};
struct dinic{
vector<Edge>edge;
vector<int>node[MAXN];
int n,m=0,s,t;
int dis[MAXN],cur[MAXN];
void addedge(int u,int v,int cap){
edge.push_back(Edge{u,v,cap,0});
edge.push_back(Edge{v,u,0,0});
node[u].push_back(m++);
node[v].push_back(m++);
}
bool bfs(){
static bool vis[MAXN];
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(s);
vis[s]=1;
dis[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<node[u].size();++i){
Edge& e=edge[node[u][i]];
if(!vis[e.v]&&e.cap>e.flow){
dis[e.v]=dis[u]+1;
vis[e.v]=1;
q.push(e.v);
}
}
}
return vis[t];
}
int dfs(int u,int a){
if(u==t||!a) return a;
int flow=0,f;
for(int& i=cur[u];i<node[u].size();++i){
Edge& e=edge[node[u][i]];
if(dis[u]+1==dis[e.v]&&(f=dfs(e.v,min(a,e.cap-e.flow)))>0){
flow+=f;
e.flow+=f;
edge[node[u][i]^1].flow-=f;
a-=f;
if(!a) break;
}
}
return flow;
}
int maxflow(){
int flow=0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
}G;
void init(){
int n=read();
int m=read();
G.n=n;
G.s=0;
G.t=n+m+1;
for(int i=1;i<=n;++i){
int x=read();
ans+=x;
G.addedge(0,i,x);
string s;
getline(cin,s);
s+=" ";
int sn=s.size();
int out=0;
bool flag=0;
for(int j=0;j<sn;++j){
if(s[j]<=57&&s[j]>=48){
out=(out<<1)+(out<<3)+s[j]-48;
flag=1;
}
else if(s[j]==32){
G.addedge(i,out+n,INF);
out=0;
flag=0;
}
}
}
for(int i=1;i<=m;++i){
int x=read();
G.addedge(i+n,G.t,x);
}
}
void print(){
int n=G.n;
ans-=G.maxflow();
for(int i=0;i<=G.m;i+=2){
Edge e=G.edge[i];
if(e.flow&&e.v<=n){
write(e.v);
putchar(32);
}
}
putchar(10);
for(int i=0;i<=G.m;i+=2){
Edge e=G.edge[i];
if(e.flow&&e.u>n){
write(e.u-n);
putchar(32);
}
}
putchar(10);
write(ans);
}
int main(){
init();
print();
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...