Bribing FIPA

C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 756K, 提交时间: 2022-09-15 19:05:28

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int inf = 1e9;
void solve(int n, int m) {
    map<string, int> mp;
    auto get = [&](string s) {
        if (!mp.count(s)) {
            int sz = mp.size();
            mp[s] = sz;
        }
        return mp[s];
    };
    vector<vector<int>> e(n + 1);
    vector<int> a(n + 1), deg(n);
    for (int i = 1; i <= n; i++) {
        string tmp, s, t;
        getline(cin, tmp);
        stringstream ss;
        ss << tmp;
        ss >> s >> a[get(s)];
        while (ss >> t) {
            e[get(s)].push_back(get(t));
            deg[get(t)]++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (deg[i] == 0) {
            e[n].push_back(i);
        }
    }
    a[n] = inf;
    vector dp(n + 1, vector<int>(n + 2, inf));
    vector<int> sz(n + 1);
    function<void(int)> dfs = [&](int u) {
        dp[u][0] = 0;
        for (int v : e[u]) {
            dfs(v);
            vector<int> tmp(n + 2, inf);
            for (int i = 0; i <= sz[u]; i++) {
                for (int j = 0; j <= sz[v]; j++) {
                    tmp[i + j] = min(tmp[i + j], dp[u][i] + dp[v][j]);
                }
            }
            sz[u] += sz[v];
            dp[u] = tmp;
        }
        sz[u] += 1;
        dp[u][sz[u]] = a[u];
    };
    dfs(n);
    int ans = inf;
    for (int i = m; i <= n + 1; i++) {
        ans = min(ans, dp[n][i]);
    }
    cout << ans << '\n';
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (true) {
        string tmp;
        getline(cin, tmp);
        if (tmp[0] == '#') break;
        int n, m;
        stringstream ss;
        ss << tmp;
        ss >> n >> m;
        solve(n, m);
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 25ms, 内存消耗: 604K, 提交时间: 2020-08-06 16:40:37

//Author:XuHt
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 206, INF = 0x3f3f3f3f, S = 106;
int n, m, a[N], f[N][N];
map<string, int> mp;
vector<int> e[N];
bool v[N];
char s[S];

int dfs(int x) {
	for (int i = 1; i <= n; i++) f[x][i] = INF;
	f[x][0] = 0;
	int cnt = 1;
	for (unsigned int i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		cnt += dfs(y);
		for (int j = n; j >= 0; j--)
			for (int k = 0; k <= j; k++)
				f[x][j] = min(f[x][j], f[x][j-k] + f[y][k]);
	}
	f[x][cnt] = min(f[x][cnt], a[x]);
	return cnt;
}

void Bribing_FIPA() {
	sscanf(s, "%d %d", &n, &m);
	int num = 0;
	mp.clear();
	memset(v, 1, sizeof(v));
	for (int i = 0; i <= n; i++) e[i].clear();
	for (int i = 1; i <= n; i++) {
		int d;
		scanf("%s %d", s, &d);
		if (mp.find(s) == mp.end()) mp[s] = ++num;
		int x = mp[s];
		a[x] = d;
		fgets(s, sizeof(s), stdin);
		stringstream ss(s);
		string str;
		while (ss >> str) {
			if (mp.find(str) == mp.end()) mp[str] = ++num;
			int y = mp[str];
			v[y] = 0;
			e[x].push_back(y);
		}
	}
	for (int i = 1; i <= n; i++) if (v[i]) e[0].push_back(i);
	a[0] = INF;
	dfs(0);
	int ans = INF;
	for (int i = m; i <= n; i++) ans = min(ans, f[0][i]);
	cout << ans << endl;
}

int main() {
	while (fgets(s, sizeof(s), stdin) && s[0] != '#') Bribing_FIPA();
	return 0;
}

C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 876K, 提交时间: 2020-11-26 14:04:20

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int maxn=2000+10;
int n,m,w[300];
bool flag[300];
map<string,int> id;
vector<int> g[300];
int sz[300],dp[300][300];
void get_size(int u)
{
	sz[u]=1;
	for(auto v:g[u])
	{
		get_size(v);
		sz[u]+=sz[v];
	}
}
void DFS(int u)
{
	dp[u][0]=0;
	for(auto v:g[u])
	{
		DFS(v);
		for(int j=sz[u];j>=0;j--)
		for(int k=0;k<=j;k++)
		dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
		
	 } 
	 dp[u][sz[u]]=min(dp[u][sz[u]],w[u]);
}
int main()
{
	while(scanf("%d%d",&n,&m))
	{
		memset(flag,0,sizeof(flag));
		memset(sz,0,sizeof(sz));
		memset(w,0,sizeof(w));
		memset(dp,0x3f,sizeof(dp));
		for(int i=0;i<=n;i++)
		g[i].clear();
		id.clear();
		for(int i=1,cnt=0;i<=n;i++)
		{
			string s;
			int t,u,v;
			char ch;
			cin>>s>>t;
			if(!id.count(s))
			id[s]=++cnt;
			u=id[s];
			w[u]=t;
			while((ch=getchar())!='\n')
			{
				cin>>s;
				if(!id.count(s))
				id[s]=++cnt;
				v=id[s];
				flag[v]=true;
				g[u].push_back(v);
			}
		}
		w[0]=INF;
		for(int i=1;i<=n;i++)
		{
			if(!flag[i])
			g[0].push_back(i);
		}
		get_size(0);
		DFS(0);
		int ans=INF;
		for(int i=m;i<=n;i++)
		ans=min(ans,dp[0][i]);
		printf("%d\n",ans);
	}
	return 0;
}

详情