疑问
  • 板块学术版
  • 楼主Augensterm
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/9 16:17
  • 上次更新2024/7/9 17:23:12
查看原帖
疑问
774592
Augensterm楼主2024/7/9 16:17

getchar和取消同步会冲突么?

UVA1222删掉取消cin同步43行就过了

#include<bits/stdc++.h>
using namespace std;
const int N=210,Inf=0x3f3f3f3f;
int n,m;
int h[N],e[N],ne[N],idx;
int f[N][N],w[N],p[N];
bool st[N];
int cnt;
map<string,int>S;
int get(string str)
{
	if(!S.count(str))S[str]=++cnt;
	return S[str];
}
void add(int a,int b)
{
	e[idx]=b;ne[idx]=h[a];
	h[a]=idx++;
	
}

int dfs(int u)
{
	for(int i=1;i<=n;i++)f[u][i]=Inf;
	f[u][0]=0;
	int cnt=1;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		cnt+=dfs(j);
		for(int v=n;v>=0;v--)
		{
			for(int k=0;k<=v;k++)
				f[u][v]=min(f[u][v],f[j][k]+f[u][v-k]);
		}
	}
	f[u][cnt]=min(f[u][cnt],w[u]);
	return cnt;
}
	
int main()
{
	//std::ios::sync_with_stdio(false);
	while(cin>>n>>m)
	{
		getchar();
		S.clear();
		cnt=0;
		memset(st,0,sizeof st);
		memset(h,-1,sizeof h);
		idx=0;
		for(int i=0;i<n;i++)
		{
			string a,b,line;int cost;
			getline(cin,line);
			stringstream ssin(line);
			ssin>>a;ssin>>cost;
			w[get(a)]=cost;
			while(ssin>>b)
			{
				st[get(b)]=true;
				add(get(a),get(b));
			}
		}
		for(int i=1;i<=n;i++)
			if(!st[i])add(0,i);
		w[0]=Inf;
		dfs(0);
		int res=Inf;
		for(int i=m;i<=n;i++)
			res=min(res,f[0][i]);
		cout<<res<<endl;
	}
	return 0;
}

我还是太菜了

2024/7/9 16:17
加载中...