首页 > ACM题库 > HDU-杭电 > HDU 3691-Nubulsa Expo[解题报告]HOJ
2014
11-30

HDU 3691-Nubulsa Expo[解题报告]HOJ

Nubulsa Expo

问题描述 :

You may not hear about Nubulsa, an island country on the Pacific Ocean. Nubulsa is an undeveloped country and it is threatened by the rising of sea level. Scientists predict that Nubulsa will disappear by the year of 2012. Nubulsa government wants to host the 2011 Expo in their country so that even in the future, all the people in the world will remember that there was a country named “Nubulsa”.

As you know, the Expo garden is made up of many museums of different countries. In the Expo garden, there are a lot of bi-directional roads connecting those museums, and all museums are directly or indirectly connected with others. Each road has a tourist capacity which means the maximum number of people who can pass the road per second.

Because Nubulsa is not a rich country and the ticket checking machine is very expensive, the government decides that there must be only one entrance and one exit. The president has already chosen a museum as the entrance of the whole Expo garden, and it’s the Expo chief directory Wuzula’s job to choose a museum as the exit.

Wuzula has been to the Shanghai Expo, and he was frightened by the tremendous “people mountain people sea” there. He wants to control the number of people in his Expo garden. So Wuzula wants to find a suitable museum as the exit so that the “max tourists flow” of the Expo garden is the minimum. If the “max tourist flow” is W, it means that when the Expo garden comes to “stable status”, the number of tourists who enter the entrance per second is at most W. When the Expo garden is in “stable status”, it means that the number of people in the Expo garden remains unchanged.

Because there are only some posters in every museum, so Wuzula assume that all tourists just keep walking and even when they come to a museum, they just walk through, never stay.

输入:

There are several test cases, and the input ends with a line of “0 0 0”.

For each test case:

The first line contains three integers N, M and S, representing the number of the museums, the number of roads and the No. of the museum which is chosen as the entrance (all museums are numbered from 1 to N). For example, 5 5 1 means that there are 5 museums and 5 roads connecting them, and the No. 1 museum is the entrance.

The next M lines describe the roads. Each line contains three integers X, Y and K, representing the road connects museum X with museum Y directly and its tourist capacity is K.

Please note:

1<N<=300, 0<M<=50000, 0<S,X,Y<=N, 0<K<=1000000

输出:

There are several test cases, and the input ends with a line of “0 0 0”.

For each test case:

The first line contains three integers N, M and S, representing the number of the museums, the number of roads and the No. of the museum which is chosen as the entrance (all museums are numbered from 1 to N). For example, 5 5 1 means that there are 5 museums and 5 roads connecting them, and the No. 1 museum is the entrance.

The next M lines describe the roads. Each line contains three integers X, Y and K, representing the road connects museum X with museum Y directly and its tourist capacity is K.

Please note:

1<N<=300, 0<M<=50000, 0<S,X,Y<=N, 0<K<=1000000

样例输入:

5 5 1
1 2 5
2 4 6
1 3 7
3 4 3
5 1 10
0 0 0

样例输出:

8

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define INF 305
#define inf 0x0f0f0f0f

using namespace std;
int cap[INF][INF],Dfn[INF],Wage[INF];
void Pre_gragh(int i,int j,int c)
{
 cap[i][j]+=c,cap[j][i]+=c;
}
int Stoer_Wagner(int n)
{
 int mincut=inf,i,j,now,t;
 for (i=1;i<=n;i++) Dfn[i]=i;
 for (;n>1;n--)
 {
 memset(Wage,0,sizeof(Wage));
 for (i=1;i<=n;i++,swap(Dfn[i],Dfn[now]))
 for (now=j=i+1;j<=n;j++)
 if (t=Dfn[j],Wage[t]+=cap[Dfn[i]][t],Wage[Dfn[now]]<Wage[t])
 now=j;
 mincut=min(mincut,Wage[Dfn[n]]);
 for (i=1;i<=n-1;i++)
 now=cap[Dfn[i]][Dfn[n]],
 cap[Dfn[i]][Dfn[n-1]]+=now,
 cap[Dfn[n-1]][Dfn[i]]+=now;
 }
 return mincut;
}
int main()
{
 int n,m,k,i,x,y,z;
 while (scanf("%d%d%d",&n,&m,&k),n)
 {
 memset(cap,0,sizeof(cap));
 for (i=1;i<=m;i++)
 scanf("%d%d%d",&x,&y,&z),Pre_gragh(x,y,z);
 printf("%d\n",Stoer_Wagner(n));
 }
 return 0;
}

  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  4. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c