hoj 2503 Bribing FIPA
Bribing FIPA
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 DCName1 DCName2 ...
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 DCName1 DCName2 ... 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
20
먼저 토폴로지 정렬을 하고 같은 나무를 한데 놓으면 뿌리 노드가 마지막에 있고 잎 노드가 맨 앞에 있는 다음에 순서에 따라 각 노드에 f[i][j]f[i][j]는 이전 i개에서 j개를 취하는 최소 값 이동 방정식을 나타낸다. if(j>=i-pre[i]) f[i]=min(f[i-1][j], f[pre[i]][j-(i-pre[i])]+dia[order[i]);elsef[i][j] = min(f[i-1][j],dia[order[i]]);그 중에서pre[i]는 i자 나무의 이전 노드 위치order[i]는 토폴로지 정렬 후의 노드 순서 dia[i]는 i점의 가치입니다. 이 문제는 악!!!
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <string>
#include <sstream>
#include <iostream>
#define N 2100
#define L 110
#define INF 111111111
using namespace std;
char name[N][L];
char st[N*L];
int n,m;
int tot_name,tot_edge;
struct CEdge
{
int m_nV;
CEdge *m_pNext;
}*adj[N],edge[N];
int f[N][N];
int pre[N];
int order[N];
int rank;
int dia[N];
bool HasFather[N];
void PushEdge(int u,int v)
{
edge[tot_edge].m_nV = v;
edge[tot_edge].m_pNext = adj[u];
adj[u] = &edge[tot_edge++];
}
int find(char *st)
{
for(int i = 0 ; i < tot_name ; i++)
{
if(!strcmp(name[i],st))return i;
}
strcpy(name[tot_name],st);
return tot_name++;
}
void Init()
{
tot_name = 0;
tot_edge = 0;
memset(HasFather,false,sizeof(HasFather));
memset(adj,0,sizeof(adj));
}
void Input()
{
gets(st);
char CouNa[L];
char DCName[L];
int DiaCou;
for(int i = 0 ; i < n ; i++ )
{
gets(st);
stringstream ssin(st);
ssin>>CouNa>>DiaCou;
int u = find(CouNa);
dia[u] = DiaCou;
while(ssin>>DCName)
{
int v = find(DCName);
PushEdge(u,v);
HasFather[v]=true;
}
}
}
void dfs(int k)
{
CEdge *temp = adj[k];
int tk = rank;
while(temp)
{
int j = temp->m_nV;
dfs(j);
temp = temp->m_pNext;
}
pre[rank]=tk-1;
order[rank++]=k;
}
void Solve()
{
rank=1;
for(int i = 0 ; i < n ; i++ )
{
if(!HasFather[i])dfs(i);
}
f[0][0] = 0;
f[0][1] = INF;
for(int i = 1 ; i <= n ; i++ )
{
f[i][i+1] = INF;
for(int j = min(m,i);j>0;j--)
{
if(j>=i-pre[i])
f[i][j] = min(f[i-1][j],f[pre[i]][j-(i-pre[i])]+dia[order[i]]);
else
f[i][j] = min(f[i-1][j],dia[order[i]]);
}
}
printf("%d
",f[n][m]);
}
int main()
{
while(scanf("%d %d",&n,&m)==2)
{
Init();
Input();
Solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[SwiftUI]List화한 CoreData를 가로 스와이프로 행 삭제하는 방법상당히 조사했지만 일본어 자료가 없었기 때문에 비망록으로 남겨 둔다. 아래와 같이 CoreData를 참조한 리스트를 가로 스와이프로 삭제하고 싶었다. UI 요소뿐만 아니라 원본 데이터 당 삭제합니다. 잘 다른 페이지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.