Massive Algorithms: Bribing FIPA: HDU-2415, POJ-3345

Bribing FIPA: HDU-2415, POJ-3345

Description

There is going to be a voting at FIPA (Fédération Internationale de Programmation Association) to determine the host of the next IPWC (International Programming World Cup). Benjamin Bennett, the delegation of Diamondland to FIPA, is trying to seek other delegation's support for a vote in favor of hosting IWPC in Diamondland. Ben is trying to buy the votes by diamond gifts. He has figured out the voting price of each and every country. However, he knows that there is no need to diamond-bribe every country, since there are small poor countries that take vote orders from their respected superpowers. So, if you bribe a country, you have gained the vote of any other country under its domination (both directly and via other countries domination). For example, if C is under domination of B, and B is under domination of A, one may get the vote of all three countries just by bribing A. Note that no country is under domination of more than one country, and the domination relationship makes no cycle. You are to help him, against a big diamond, by writing a program to find out the minimum number of diamonds needed such that at least m countries vote in favor of Diamondland. Since Diamondland is a candidate, it stands out of the voting process.

Input

The input consists of multiple test cases. Each test case starts with a line containing two integers n (1 ≤ n ≤ 200) and m (0 ≤ m ≤ n) which are the number of countries participating in the voting process, and the number of votes Diamondland needs. The next n lines, each describing one country, are of the following form:
CountryName DiamondCount DCName₁ DCName₁ ...
CountryName, the name of the country, is a string of at least one and at most 100 letters and DiamondCount is a positive integer which is the number of diamonds needed to get the vote of that country and all of the countries that their names come in the list DCName₁ DCName₁ ... which means they are under direct domination of that country. Note that it is possible that some countries do not have any other country under domination. The end of the input is marked by a single line containing a single # character.

Output

For each test case, write a single line containing a number showing the minimum number of diamonds needed to gain the vote of at least m countries.

Sample Input

3 2
Aland 10
Boland 20 Aland
Coland 15
#

Sample Output

http://blog.csdn.net/shuangde800/article/details/10276541
有n个国家，你要获取m个国家的支持，获取第i个国家的支持就要给cost[i]的价, 其中有一些国家是老大和小弟的关系，也就是说，如果你获得了某个老大国家的支持，那么这个国家的所有小弟(包括小弟的小弟...递归下去)都会无偿免费支持你。问最少的花费可以得到m个国家的支持.

老大和小弟的关系，其实就是组成了一棵棵的树，那么所有国家的关系就是一个森林。
为了方便进行树形dp，在增加一个“超级根节点”，森林里所有树的根节点是“超级根节点”的儿子。
那么，用f(i, j)表示子树i, 获取j个国家支持的最少花费
对于子树i，所有节点i的儿子节点都是一组物品，
对于某个儿子，可以选择让他支持1,2..,j个，那么就是对所有儿子进行分组背包了。。
用tot[v]表示子树v的节点个数
状态转移为：

f[u][i] = min{ f[u][i], f[u][i-j] + f[v][j] | 1<=j<=tot[v] && j<=i && v是u的儿子 };

http://blog.csdn.net/zhanghan735/article/details/9388443

由于可能有多个国家没有被控制，即其关系森林，可以加一个点0，让所有没被控制的国家成为o点的附属国

dp[i][k]表示以i为顶点的子树下贿赂k个国家需要的最少钱数：

当其为叶子结点时dp[i][0]=0;dp[i][1]=cost[i]

当其不是叶子结点时：dp[i][k]=min(dp[i][k],dp[i][k-j]+dp[t][j])(t是i的子树顶点)

map<string,int> pq;
int maze[N][N];
int dem[N][2];//dem[i][0]表示贿赂i国需要的花费，dem[i][1]表示i国控制的国家数+自己
int indeg[N];//每个点的入度
int p;
int n,m;
int dp[N][N];//d[i][j]表示以i为顶点的子树中选j个需要的花费
int dfs(int s)
{
int num=1;
if(s==0)num=0;
if(dem[s][1]==1&&s!=0)
{
dp[s][0]=0;
dp[s][1]=dem[s][0];
return 1;
}
for(int i=1;i<=n;i++)
{
if(maze[s][i]==0)
num+=dfs(i);
}
dp[s][0]=0;
for(int i=1;i<=n;i++) //这里是表示两个子树的合并，要仔细理解
{ if(maze[s][i]==-1)continue;
for(int k=n;k>=0;k--)
{
for(int j=1;j<=k;j++)
{
if(dp[s][k-j]!=-1&&dp[i][j]!=-1)
{ if(dp[s][k]!=-1)
dp[s][k]=min(dp[s][k],dp[s][k-j]+dp[i][j]);
else
dp[s][k]= dp[s][k-j]+dp[i][j];
}
}
}
}
if(dp[s][num]==-1||dp[s][num]>dem[s][0])
dp[s][num]=dem[s][0];
return num;
}
int main()
{
char c1[20],c2[20];
//freopen("in.txt","r",stdin);
string s1,s2;
while(scanf("%s %s",c1,c2)&&c1[0]!='#')//#是表示在文件的结尾，不是每组输入的结尾
{
sscanf(c1,"%d",&n);
sscanf(c2,"%d",&m);
getchar();
p=1;
memset(maze,-1,sizeof(maze));
memset(indeg,0,sizeof(indeg));
for(int i=0;i<n;i++)
{ cin>>s1;
if(pq[s1]==0)
pq[s1]=p++;
int s=pq[s1];
cin>>dem[s][0];
dem[s][1]=1;
char ch=getchar();
while(ch!='\n')
{
cin>>s2;
if(pq[s2]==0)
pq[s2]=p++;
maze[s][pq[s2]]=0;
indeg[pq[s2]]++;
dem[s][1]++;
ch=getchar();
}
}
dem[0][0]=0;
dem[0][1]=1;
for(int i=1;i<=n;i++)
if(indeg[i]==0)
{maze[0][i]=0;
dem[0][1]++;
dem[0][0]+=dem[i][0];
}
memset(dp,-1,sizeof(dp));
dfs(0);
int ans=inf;
for(int j=m;j<=n;j++)
if(dp[0][j]!=-1&&dp[0][j]<ans)
{ans=dp[0][j];
}
printf("%d\n",ans);
pq.clear();
}
return 0;
}

http://blog.csdn.net/shuangde800/article/details/10276541


vector<int>adj[MAXN];

map<string, int>name;

int cost[MAXN];

int f[MAXN][MAXN];

int tot[MAXN];

bool deg[MAXN];

vector<string>str[MAXN];

char buf[MAXN], buf2[MAXN];

int n, m;



inline void read() {



    // clear

    for (int i = 0; i <= n; ++i)

        adj[i].clear(), str[i].clear();

    name.clear();



    int idx = 1;

    // read

    string buf;

    for (int i = 1; i <= n; ++i) { 

        getline(cin, buf);

        stringstream sin(buf);

        string s;

        int v;

        sin >> s >> cost[i];

        name[s] = i;

        while (sin >> s) {

            str[i].push_back(s); 

        }

    }



    memset(deg, 0, sizeof(deg));

    for (int i = 1; i <= n; ++i) {

        for (int e = 0; e < str[i].size(); ++e) {

            int v = name[str[i][e]];

            adj[i].push_back(v);

            deg[v] = true;

        }  

    }



    for (int i = 1; i <= n; ++i)

        if (!deg[i])

            adj[0].push_back(i);

} 



int dfs(int u) {

    tot[u] = 1;



    // count vertex

    for (int e = 0; e < adj[u].size(); ++e) {

        int v = adj[u][e];

        tot[u] += dfs(v);

    }



    // init

    f[u][0] = 0;

    f[u][1] = cost[u];

    if (u) {

        for (int i = 1; i <= tot[u]; ++i)

            f[u][i] = cost[u];

    }

    // dp

    for (int e = 0; e < adj[u].size(); ++e) {

        int v = adj[u][e];

        for (int i = tot[u]; i >= 1; --i) {

            for (int j = 1; j <= tot[v] && j <= i; ++j) 

                f[u][i] = min(f[u][i], f[u][i-j] + f[v][j]); 

        }

    }

    return tot[u];

}



int main(){



    while (gets(buf) && buf[0] != '#'){



        sscanf(buf, "%d%d", &n, &m);

        read();

        memset(f, INF, sizeof(f));

        dfs(0);

        int ans = INF;

        for (int i = m+1; i <= n+1; ++i)

            ans = min(ans, f[0][i]);

        printf("%d\n", ans);

    }



    return 0;

}

Bribing FIPA: HDU-2415, POJ-3345

Labels

Popular Posts