首页 > ACM题库 > HDU-杭电 > HDU 3987-Harry Potter and the Forbidden Forest[解题报告]HOJ
2015
04-14

HDU 3987-Harry Potter and the Forbidden Forest[解题报告]HOJ

Harry Potter and the Forbidden Forest

问题描述 :

Harry Potter notices some Death Eaters try to slip into Castle. The Death Eaters hide in the most depths of Forbidden Forest. Harry need stop them as soon as.
Harry Potter and the Final Battle

The Forbidden Forest is mysterious. It consists of N nodes numbered from 0 to N-1. All of Death Eaters stay in the node numbered 0. The position of Castle is node n-1. The nodes connected by some roads. Harry need block some roads by magic and he want to minimize the cost. But it’s not enough, Harry want to know how many roads are blocked at least.

输入:

Input consists of several test cases.

The first line is number of test case.

Each test case, the first line contains two integers n, m, which means the number of nodes and edges of the graph. Each node is numbered 0 to n-1.

Following m lines contains information about edges. Each line has four integers u, v, c, d. The first two integers mean two endpoints of the edges. The third one is cost of block the edge. The fourth one means directed (d = 0) or undirected (d = 1).

Technical Specification

1. 2 <= n <= 1000
2. 0 <= m <= 100000
3. 0 <= u, v <= n-1
4. 0 < c <= 1000000
5. 0 <= d <= 1

输出:

Input consists of several test cases.

The first line is number of test case.

Each test case, the first line contains two integers n, m, which means the number of nodes and edges of the graph. Each node is numbered 0 to n-1.

Following m lines contains information about edges. Each line has four integers u, v, c, d. The first two integers mean two endpoints of the edges. The third one is cost of block the edge. The fourth one means directed (d = 0) or undirected (d = 1).

Technical Specification

1. 2 <= n <= 1000
2. 0 <= m <= 100000
3. 0 <= u, v <= n-1
4. 0 < c <= 1000000
5. 0 <= d <= 1

样例输入:

3

4 5
0 1 3 0
0 2 1 0
1 2 1 1
1 3 1 1
2 3 3 1

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

3 6
0 1 1 0
0 1 2 0
1 1 1 1
1 2 1 0
1 2 1 0
2 1 1 1

样例输出:

Case 1: 3
Case 2: 2
Case 3: 2

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define sz 10005
#define inf 0x7fffffff
struct node{int s,t,v,nxt;}e[sz*100];
int hd[sz],dis[sz],cur[sz],que[sz],cnt;
void insert(int s,int t,int v){
 e[cnt].s=s,e[cnt].t=t,e[cnt].v=v,e[cnt].nxt=hd[s],hd[s]=cnt++;
 e[cnt].s=t,e[cnt].t=s,e[cnt].v=0,e[cnt].nxt=hd[t],hd[t]=cnt++;
}
bool bfs(int s,int t,int n){
 int head=0,tail=0,i;
 memset(dis,-1,sizeof(dis[0])*(n+1)),dis[s]=0;
 que[tail++]=s;
 while(head<tail){
 for(i=hd[que[head++]];i!=-1;i=e[i].nxt)
 if(e[i].v>0&&dis[e[i].t]==-1){
 dis[e[i].t]=dis[e[i].s]+1;
 if(e[i].t==t)return 1;
 que[tail++]=e[i].t;
 }
 }
 return 0;
}
int dinic(int s,int t,int n){
 int i,mf=0,tp;
 while(bfs(s,t,n)){
 for(i=0;i<n;i++)cur[i]=hd[i];
 int u=s,tail=0;
 while(cur[s]!=-1){
 if(u!=t&&cur[u]!=-1&&e[cur[u]].v>0&&dis[u]+1==dis[e[cur[u]].t]){
 que[tail++]=cur[u];u=e[cur[u]].t;
 }
 else if(u==t){
 for(tp=inf,i=tail-1;i>=0;i--)tp=min(tp,e[que[i]].v);
 for(mf+=tp,i=tail-1;i>=0;i--){
 e[que[i]].v-=tp;e[que[i]^1].v+=tp;
 if(e[que[i]].v==0)tail=i;
 }
 u=e[que[tail]].s;
 }
 else {
 while(u!=s&&cur[u]==-1)u=e[que[--tail]].s;
 cur[u]=e[cur[u]].nxt;
 }
 }
 }
 return mf;
}
int main(){
 int T,n,m,s,t,c,flag;
 scanf("%d",&T);
 for(int cas=1;cas<=T;cas++){
 scanf("%d%d",&n,&m);
 memset(hd,-1,sizeof(hd));
 cnt = 0;
 while(m--){
 scanf("%d%d%d%d",&s,&t,&c,&flag);
 if(flag){
 insert(t,s,c);
 }
 insert(s,t,c);
 }
 int ans = dinic(0,n-1,n);
 // cout<<ans<<endl;

 for(int i=0;i<cnt;i+=2){
 if(e[i].v==0){
 e[i].v=1;
 e[i^1].v=0;
 }
 else {
 e[i].v=inf;
 e[i^1].v=0;
 }
 }

 printf("Case %d: %d\n",cas,dinic(0,n-1,n));
 }
}

  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

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