蒟蒻0分求调
查看原帖
蒟蒻0分求调
544233
coolcoder楼主2024/4/6 08:51

很奇怪

交了0分,下了第一个数据,发现就是给的样例,本地跑的没一点问题,答案17,但是测试点信息说我的答案是35

各位大佬能看看我这是什么问题吗 (读入是复制的另一个讨论的)

提交记录

CODE:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=150,M=3000;
const int Inf=1e8;

int n,m;
int s,t;

int hd[N],edg[M],cap[M],nxt[M],idx;
int dep[N],cur[N];

void adde(int u,int v,int w) {
	edg[idx]=v,cap[idx]=w,nxt[idx]=hd[u],hd[u]=idx++;
	edg[idx]=u,cap[idx]=0,nxt[idx]=hd[v],hd[v]=idx++;
}

int nail;
string str;

int read() {
	if(nail>=str.size()) return 0;
	int b=0;
	while(nail<str.size()&&(str[nail]<'0'||str[nail]>'9')) nail++;
	while(nail<str.size()&&str[nail]>='0'&&str[nail]<='9') {
		b=b*10+str[nail]-'0';
		nail++;
	}
	return b;
}

bool bfs() {
	queue<int> q;
	memset(dep,-1,sizeof(dep));
	dep[s]=0,cur[s]=hd[s];
	q.push(s);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=hd[u];~i;i=nxt[i]) {
			int v=edg[i];
			if(dep[v]==-1&&cap[i]) {
				dep[v]=dep[u]+1;
				cur[v]=hd[v];
				if(v==t) return true;
				q.push(v);
			}
		}
	}
	return false;
}

int dfs(int u,int lim) {
	if(u==t) return lim;
	int flw=0;
	for(int i=cur[u];~i&&flw<lim;i=nxt[i]) {
		cur[u]=i;
		int v=edg[i];
		if(dep[v]==dep[u]+1&&cap[i]) {
			int tmp=dfs(v,min(cap[i],lim-flw));
			if(!tmp) dep[v]=-1;
			cap[i]-=tmp,cap[i^1]+=tmp;
			flw+=tmp;
		}
	}
	return flw;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	memset(hd,-1,sizeof(hd));
	cin>>n>>m;
	getline(cin,str);
	int res;
	int sum=0;
	s=0,t=n+m+1;
	for(int i=1;i<=n;i++){
		nail=0;
		getline(cin,str);
		res=read();
		sum+=res;
		adde(s,i,res);
		while(true) {
			res=read();
			adde(i,res+n,Inf);
			if(!res) break;
		}
	}
	for(int i=1;i<=m;i++) {
		int x;
		scanf("%d",&x);
		adde(i+n,t,x);
	}
	res=0;
	int flw;
	while(bfs()) while(flw=dfs(s,Inf)) res+=flw;
	int answ[N],cont=0;
	for(int i=hd[s];~i;i=nxt[i]) {
		if(cap[i]) answ[++cont]=edg[i];
	}
	while(cont) {
		cout<<answ[cont]<<' ';
		cont--;
	}
	cout<<'\n';
	cont=0;
	for(int i=hd[t];~i;i=nxt[i]) {
		if(cap[i]) answ[++cont]=edg[i]-n;
	}
	while(cont) {
		cout<<answ[cont]<<' ';
		cont--;
	}
	cout<<'\n';
	cout<<sum-res<<endl;
	
	return 0;
}
2024/4/6 08:51
加载中...