迷之33分
查看原帖
迷之33分
398312
国王的新账号楼主2021/7/30 16:30

好像错的和其他人不太一样(可是我真的找不出错了)

#include<bits/stdc++.h>
using namespace std;
const int maxn=100006;
const int inf=2e9+6;
int cnt=1,s,t,n,m,tot;
int head[maxn],dep[maxn];
struct Edge{
	int to,nxt,w;
}e[maxn];
void add(int u,int v,int w)
{
	e[++cnt].w=w;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
bool bfs()
{
	memset(dep,0,sizeof(dep));
	queue<int>q;
	dep[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i>1;i=e[i].nxt){
			int w=e[i].w,v=e[i].to;
			if(w>0&&!dep[v]){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]!=0;
}
int dfs(int u,int lim)
{
	if(u==t)	return lim;
	int delta=lim;
	for(int i=head[u];i>1;i=e[i].nxt){
		int w=e[i].w,v=e[i].to;
		if(w>0&&dep[v]==dep[u]+1){
			int d=dfs(v,min(w,lim));
			if(d>0){
				e[i].w-=d;
				e[i^1].w+=d;
			}
			delta-=d;
			if(delta==0)	break;
		}
	}
	if(delta==lim)	dep[u]=0;
	return lim-delta;
}
int dini()
{
	int res=0;
	while(bfs()){
		res+=dfs(s,0x7f7f7f7f);
	}
	return res;
}
int main()
{
	scanf("%d%d",&m,&n);
	s=0,t=n+m+1;
	char ch[maxn];
	for(int i=1;i<=m;++i){
		cin.getline(ch,1000);
		int len=strlen(ch);
		if(len<=1){
			--i;
			continue;
		} 
		int now=0,p=0,f=1;
		while(p<=len){
			if(isdigit(ch[p])){
				now=now*10+ch[p]-'0';
			}else{
				if(f){
					add(s,i,now);
					add(i,s,0);
					f=0;
					tot+=now;
				}else{
					add(i,now+m,inf);
					add(now+m,i,0);
				}
				now=0;
			}
			++p;
		}
	}
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		add(i+m,t,x);
		add(t,i+m,0);
	}
	int ans=tot-dini();
	for(int i=1;i<=m;i++){
		if(dep[i]!=0)	printf("%d ",i);
	}
	printf("\n");
	for(int i=1;i<=n;i++){
		if(dep[i+m]!=0)	printf("%d ",i);
	}
	printf("\n%d",ans);
	return 0;
}

求dalao教教我吧

2021/7/30 16:30
加载中...