[UVA][SCC、暴搜] 11390 - The Sultan's Feast
|
I I U C O N L I N E C O N T E S T 2 0 0 8 |
|
|
Problem F: The Sultan’s Feast |
|
|
Input: standard input Output: standard output |
|
|
|
|
|
Our beloved sultan is back again, and he is really excited. He will be celebrating his 2nd year anniversary next month. He is arranging a feast for that. But that is where, he is facing some problems.
He is holding a grand feast, and every guest can bring any number of guests. And there guests can also bring their guests and so on. The problem is, he doesn’t like everyone, and dislike many of the guests. So, he decided, he won’t be inviting every one.
He has assigned a ‘like’ value to everyone in his guest list. If like value is positive, then he likes them, negative if he dislikes, and zero if neither.
Now, sultan wants to invite his friends in such a way that would maximize the sum of ‘like’ value of all guests.
|
|
|
Input |
|
|
First line contains T, the number of test cases. Each test case starts with an integer N, the number of people in the guest list. The following N lines each starts with two integers, li and ri. li is the ‘like’ value of the i-th person, and ri is the number of people he likes to invite. Rest of the line contains ri integers, the other guests i-th guest likes to invite. All guests are numbered from 1 to N. There is a blank line before each test case.
|
|
|
Output |
|
|
For each test case, output the case number followed by the maximum ‘like’ value, or print “Alas, sultan can't invite anyone!” if it’s not possible to invite anyone. Sultan can invite, as long as the sum is non negative.
|
|
|
Constraints |
|
|
- T ≤ 100 - N ≤ 100 - -10000 ≤ li ≤ 10000, for all i = 1, 2, …, N - 1 ≤ ri ≤ N – 1 - In the friend list, no person is listed twice, and all numbers in the list are between 1 and N.
|
|
|
Sample Input |
Output for Sample Input |
|
3
5 8 2 2 4 -9 1 5 7 1 4 0 1 5 -10 0
4 10 2 2 4 -2 1 4 12 1 4 -10 0
5 10 1 2 -12 1 3 2 1 5 12 1 5 -10 0 |
Case #1: Alas, sultan can't invite anyone! Case #2: 10 Case #3: 4 |
|
|
|
|
Problem setter: Manzurur Rahman Khan |
|
每個人都有一個好感度 L[i]，一旦邀請其中一個人時，會連通他的親朋友們一起拉上來。
求會場好感度總和最大為多少。
題目解法：
使用 SCC 壓縮一些連通元件，只是把數據壓小而已。
即使在 DAG 圖中，假設選擇兩個參加，仍有可能產生重疊的親朋好友，在操作上沒辦法切割。
所以採用暴搜的方式去找尋解，而窮舉層面又可以考慮到每次只邀請好感度 >= 0 的。
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
vector<int> g[105], dag[105];
int vfind[105], findIdx;
int stk[105], stkIdx;
int in_stk[105], visited[105];
int contract[105];
int scc(int nd) {
in_stk[nd] = visited[nd] = 1;
stk[++stkIdx] = nd;
vfind[nd] = ++findIdx;
int mn = vfind[nd];
for(int i = 0; i < g[nd].size(); i++) {
if(!visited[g[nd][i]])
mn = min(mn, scc(g[nd][i]));
if(in_stk[g[nd][i]])
mn = min(mn, vfind[g[nd][i]]);
}
if(mn == vfind[nd]) {
do {
in_stk[stk[stkIdx]] = 0;
contract[stk[stkIdx]] = nd;
} while(stk[stkIdx--] != nd);
}
return mn;
}
int L[105], val_L[105], next_search[105];
int invited[105], max_like;
vector<int> cover[105];
int H() {
int ret = 0;
for(int i = next_search[0]; i != -1; i = next_search[i]) {
if(invited[i] == 0)
ret += val_L[i];
}
return ret;
}
int get_like(int idx) {
int ret = 0;
for(int i = 0; i < cover[idx].size(); i++) {
int y = cover[idx][i];
if(invited[y] == 0)
ret += val_L[y];
invited[y]++;
}
return ret;
}
void remove_like(int idx) {
for(int i = 0; i < cover[idx].size(); i++) {
int y = cover[idx][i];
invited[y]--;
}
}
void dfs(int idx, int like, int s) {
if(s)
max_like = max(max_like, like);
if(idx == -1 || like + H() <= max_like)
return ;
if(invited[idx] == 0) {
int f = get_like(idx);
dfs(next_search[idx], like + f, 1);
remove_like(idx);
}
dfs(next_search[idx], like, s);
}
void bfs(int idx) {
int visited[105] = {};
queue<int> Q;
Q.push(idx), visited[idx] = 1;
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
cover[idx].push_back(tn);
for(int i = 0; i < dag[tn].size(); i++) {
int y = dag[tn][i];
if(visited[y] == 0) {
visited[y] = 1;
Q.push(y);
}
}
}
}
int main() {
int testcase, cases = 0;
int n, m, x, y;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i <= n; i++) {
g[i].clear();
dag[i].clear();
cover[i].clear();
val_L[i] = 0;
invited[i] = 0;
}
for(i = 1; i <= n; i++) {
scanf("%d %d", &L[i], &m);
while(m--) {
scanf("%d", &x);
g[i].push_back(x);
}
}
// SCC
memset(visited, 0, sizeof(visited));
memset(in_stk, 0, sizeof(in_stk));
for(i = 1; i <= n; i++) {
if(!visited[i]) {
findIdx = stkIdx = 0;
scc(i);
}
}
//
for(i = 1; i <= n; i++) {
x = contract[i];
val_L[x] += L[i];
for(vector<int>::iterator it = g[i].begin();
it != g[i].end(); it++) {
y = contract[*it];
if(x != y)
dag[x].push_back(y);
}
}
//
int prev = -1;
for(i = n; i >= 0; i--) {
next_search[i] = prev;
if(val_L[i] >= 0 && contract[i] == i)
prev = i;
}
for(i = 1; i <= n; i++)
bfs(i);
max_like = -1;
dfs(next_search[0], 0, 0);
printf("Case #%d: ", ++cases);
if(max_like < 0)
puts("Alas, sultan can't invite anyone!");
else
printf("%d\n", max_like);
}
return 0;
}