2014
03-02

The Heart of the Country

The nation of Graphia is at war. The neighboring nations have for long watched in jealousy as Graphia erected prosperous cities and connected them with a network of highways. Now they want a piece of the pie.

Graphia consists of several cities, connected by highways. Graphian terrain is rough, so the only way to move between the cities is along the highways. Each city has a certain number of troops quartered there. Graphia’s military command knows that it will require a certain number of troops, K , to defend any city. They can defend a city with the troops stationed there, supported by the troops in any other city which is directly connected with a highway, with no cities in between. Any troops further away than that simply cannot get there in time. They also know that their enemies will onlyattack one city at a time — so the troops in a city can be used to defend that city, as well as any of its neighbors. However, if a city can’t be defended, then the military command must assume that the troops quartered in that city will be captured, and cannot aid in the defense of Graphia. In the case below, suppose K = 10 . City C might seem well defended, but it will eventually fall.

Graphia’s leadership wants to identify the Heart of their country — the largest possible group of cities that can mutually defend each other, even if all of the other cities fall.

More formally, a city is defensible if it can draw a total of at least K troops from itself, and from cities directly adjacent to it. A set of cities is defensible if every city in it is defensible, using only troops from itself and adjacent cities in that set. The Heart of the country is the largest possible defensible set of cities – that is, no other defensible set of cities has more cities in it.

There will be several data sets. Each set begins with two integers, N and K , where N is the number of cities ( 3<=N<=1000 ), and K is the number of troops required to defend a city. The cities are numbered 0 through N – 1 .

On the next N lines are descriptions of the cities, starting with city 0. Each of the city description lines begins with an integer T , indicating the number of troops quartered in that city ( 0<=T<=10000 ). This is followed by an integer M , indicating the number of highways going out of that city, and then M integers, indicating the cities those highways go to. No two highways will go from and to the same cities, so every city in each list will be unique. No highway will loop from a city back to the same city. The highways go both ways, so that if city I is in city J ‘s list, then it’s guaranteed that city J will be in city I ‘s list in the input. The input will end with a line with two space-separated 0′s.

There will be several data sets. Each set begins with two integers, N and K , where N is the number of cities ( 3<=N<=1000 ), and K is the number of troops required to defend a city. The cities are numbered 0 through N – 1 .

On the next N lines are descriptions of the cities, starting with city 0. Each of the city description lines begins with an integer T , indicating the number of troops quartered in that city ( 0<=T<=10000 ). This is followed by an integer M , indicating the number of highways going out of that city, and then M integers, indicating the cities those highways go to. No two highways will go from and to the same cities, so every city in each list will be unique. No highway will loop from a city back to the same city. The highways go both ways, so that if city I is in city J ‘s list, then it’s guaranteed that city J will be in city I ‘s list in the input. The input will end with a line with two space-separated 0′s.

4 900
100 2 1 2
200 2 0 3
500 2 0 3
1000 2 1 2
4 900
100 3 1 2 3
200 3 0 3 2
500 3 1 3 0
1000 3 2 1 0
0 0

3 1700
4 1800

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 1010
using namespace std;

queue<int> q;

int val[N],n,k,sum[N];
vector <int> g[N];
bool vis[N];
int ans;

void init (){
for (int i = 0;i <= n;i ++){
g[i].clear();
vis[i] = true;
sum[i] = 0;
ans = 0;
}
while (!q.empty()) q.pop();
}

void process (){
while (!q.empty()) {
int u = q.front();
q.pop();
int sz = g[u].size();
for (int i = 0;i < sz;i ++){
int v = g[u][i];
if (!vis[v]) continue;
sum[v] -= val[u];
if (sum[v] < k){
vis[v] = false;
q.push(v);
ans -= val[v];
}
}
}
int t = 0;
for (int i = 0;i < n;i ++)
if (vis[i]) t ++;
printf ("%d %d\n",t,ans);
}
int main (){
int t,x;
while (~scanf ("%d%d",&n,&k)) {
if (n + k == 0) break;
init();
for (int i = 0;i < n;i ++){
scanf ("%d",&val[i]);
ans += val[i];
scanf ("%d",&t);
while (t --){
scanf ("%d",&x);
g[i].push_back(x);
}
}
for (int i = 0;i < n;i ++){
sum[i] = val[i];
int sz = g[i].size();
for (int j = 0;j < sz;j ++){
int v = g[i][j];
sum[i] += val[v];
}
}
for (int i = 0;i < n;i ++) {
if (sum[i] < k){
q.push(i);
ans -= val[i];
vis[i] = false;
}
}
process();
}
return 0;
}

1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

3. #include <cstdio>

int main() {
int n, u, d;
while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
if(n<=u) { puts("1"); continue; }
n-=u; u-=d; n+=u-1; n/=u;
n<<=1, ++n;
printf("%dn",n);
}
return 0;
}

4. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

5. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。