mxqz,11分WA是输出的问题吗
查看原帖
mxqz,11分WA是输出的问题吗
467089
xlsfyc楼主2022/2/18 18:00

代码:

#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
int n,m,head[110]={0},d[110]={0},cnt=0,ans=0;
queue<int> q;
struct Edge{
	int to,nxt,cap,flow;
}e[10001];
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].cap=w;
	e[cnt].flow=0;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void init(){
	memset(d,0,sizeof(d));
	while(!q.empty()) q.pop();
}
bool bfs(int s,int t){
	init();
	d[s]=1,q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(d[v]==0 && e[i].cap>e[i].flow){
				d[v]=d[u]+1,q.push(v);
				if(v==t) return true;
			}
		}
	}
	return false;
}
int dfs(int u,int flow,int t){
	if(u==t) return flow;
	int rest=flow;
	for(int i=head[u];i>0 && rest>0;i=e[i].nxt){
		int v=e[i].to;
		if(d[v]==d[u]+1 && e[i].cap>e[i].flow){
			int k=dfs(v,min(rest,e[i].cap-e[i].flow),t),j=(i%2==1)?(i+1):(i-1);
			if(k==0) d[v]=0;
			e[i].flow+=k,e[j].flow-=k;
			rest-=k;
		}
	}
	return flow-rest;
}
int Dinic(int s,int t){
	int ans=0;
	while(bfs(s,t)==true) ans+=dfs(s,INF,t);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n+1;i++){
		int x;
		scanf("%d",&x);
		add(1,i,x),add(i,1,0);
		ans+=x;
		char tools[10000];
		memset(tools,0,sizeof tools);
		cin.getline(tools,10000);
		int ulen=0,tool;
		while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
		{//tool是该实验所需仪器的其中一个      
		    //这一行,你可以将读进来的编号进行储存、处理,如连边。
		    add(i,tool+n+1,INF),add(tool+n+1,i,INF);
		    if (tool==0) 
		        ulen++;
		    else {
		        while (tool) {
		            tool/=10;
		            ulen++;
		        }
		    }
		    ulen++;
		}
	}
	for(int i=n+2;i<=n+m+1;i++){
		int x;
		scanf("%d",&x);
		add(i,n+m+2,x),add(n+m+2,i,0);
	}
	ans-=Dinic(1,n+m+2);
	for(int i=2;i<=n+1;i++) if(d[i]>0) printf("%d ",i-1);
	printf("\n");
	for(int i=n+2;i<=n+m+1;i++) if(d[i]>0) printf("%d ",i-(n+1));
	printf("\n%d",ans);
	return 0;
}

读入直接用题目的了,看讨论区说输出很阴间。

太伞兵了迷惑 1111

2022/2/18 18:00
加载中...