1021 Safe Fruit
Statement
Metadata
- 作者: CHEN, Yue
- 单位: 浙江大学
- 代码长度限制: 16 KB
- 时间限制: 4000 ms
- 内存限制: 64 MB
There are a lot of tips telling us that some fruits must not be eaten with some other fruits, or we might get ourselves in serious trouble. For example, bananas can not be eaten with cantaloupe (哈密瓜), otherwise it will lead to kidney deficiency (肾虚).
Now you are given a long list of such tips, and a big basket of fruits. You are supposed to pick up those fruits so that it is safe to eat any of them.
Input Specification
Each input file contains one test case. For each case, the first line gives two positive integers: N, the number of tips, and M, the number of fruits in the basket. both numbers are no more than 100.
Then two blocks follow. The first block contains N pairs of fruits which must not be eaten together, each pair occupies a line and there is no duplicated tips; and the second one contains M fruits together with their prices, again each pair in a line. To make it simple, each fruit is represented by a 3-digit ID number. A price is a positive integer which is no more than 1000. All the numbers in a line are separated by spaces.
Output Specification
For each case, first print in a line the maximum number of safe fruits. Then in the next line list all the safe fruits, in increasing order of their ID's. The ID's must be separated by exactly one space, and there must be no extra space at the end of the line. Finally in the third line print the total price of the above fruits. Since there may be many different solutions, you are supposed to output the one with a maximum number of safe fruits. In case there is a tie, output the one with the lowest total price. It is guaranteed that such a solution is unique.
Sample Input
16 20
001 002
003 004
004 005
005 006
006 007
007 008
008 003
009 010
009 011
009 012
009 013
010 014
011 015
012 016
012 017
013 018
020 99
019 99
018 4
017 2
016 3
015 6
014 5
013 1
012 1
011 1
010 1
009 10
008 1
007 2
006 5
005 3
004 4
003 6
002 1
001 2
Sample Output
Solution
#include <bits/stdc++.h>
using namespace std;
using pII = pair<int, int>;
#define fi first
#define se second
#define SZ(x) (int(x.size()))
const int N = 110;
int n, m, w[N];
int best, Val;
int x[N], path[N];
int num[N], val[N];
int g[N][N];
//点的标号[0, n - 1]
void dfs(int *adj, int total, int cnt, int cost) { // total: 与u相连的顶点数量, cnt表示当前团的大小
int i, j, k;
int t[N];
if (total == 0) {
if (best < cnt || (best == cnt && cost < Val)) {
for (i = 0; i < cnt; i++) path[i] = x[i];
best = cnt;
Val = cost;
}
}
for (i = 0; i < total; i++) {
if (cnt + num[adj[i]] < best || (cnt + num[adj[i]] == best && cost + val[adj[i]] >= Val))
return;
x[cnt] = adj[i];
for (k = 0, j = i + 1; j < total; j++) {
if (g[adj[i]][adj[j]]) {
t[k++] = adj[j];
}
}
dfs(t, k, cnt + 1, cost + w[adj[i]]);
}
}
int MaximumClique() {
int i, j, k;
int adj[N];
best = 0;
Val = 1e9;
for (i = n - 1; i >= 0; i--) {
//保存方案
x[0] = i;
for (k = 0, j = i + 1; j < n; j++) // 遍历[i + 1, n]间顶点，
if (g[i][j])
adj[k++] = j;
dfs(adj, k, 1, w[i]); // *adj, total, cnt
num[i] = best;
val[i] = Val;
}
return best;
}
map<int, int> id, fid;
int cntID;
int getID(int d) {
if (id.count(d))
return id[d];
id[d] = cntID;
fid[cntID] = d;
++cntID;
return cntID - 1;
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = 1;
}
g[i][i] = 0;
}
cntID = 0;
vector<pII> edge;
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
edge.push_back(pII(u, v));
}
for (int i = 1, u, _w; i <= n; ++i) {
scanf("%d%d", &u, &_w);
u = getID(u);
w[u] = _w;
}
for (auto &it : edge) {
int u = getID(it.fi), v = getID(it.se);
if (u >= n || v >= n)
continue;
g[u][v] = g[v][u] = 0;
}
MaximumClique();
vector<string> vec;
for (int i = 0; i < best; ++i) {
string s = "";
int x = fid[path[i]];
while (x) {
s.push_back(x % 10 + '0');
x /= 10;
}
while (SZ(s) < 3) s.push_back('0');
reverse(s.begin(), s.end());
vec.push_back(s);
}
sort(vec.begin(), vec.end());
cout << best << "\n";
for (int i = 0; i < best; ++i) cout << vec[i] << " \n"[i == best - 1];
cout << Val << endl;
return 0;
}