首页 > ACM题库 > HDU-杭电 > hdu 2334 March of the Penguins-网络流[解题报告]C++
2014
01-05

hdu 2334 March of the Penguins-网络流[解题报告]C++

March of the Penguins

问题描述 :

Somewhere near the south pole, a number of penguins are standing on a number of ice floes. Being social animals, the penguins would like to get together, all on the same floe. The penguins do not want to get wet, so they have use their limited jump distance to get together by jumping from piece to piece. However, temperatures have been high lately, and the floes are showing cracks, and they get damaged further by the force needed to jump to another floe. Fortunately the penguins are real experts on cracking ice floes, and know exactly how many times a penguin can jump off each floe before it disintegrates and disappears. Landing on an ice floe does not damage it. You have to help the penguins find all floes where they can meet.


A sample layout of ice floes with 3 penguins on them.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with the integer N (1 ≤ N ≤ 100) and a floating-point number D (0 ≤ D ≤ 100 000), denoting the number of ice pieces and the maximum distance a penguin can jump.

N lines, each line containing xi, yi, ni and mi, denoting for each ice piece its X and Y coordinate, the number of penguins on it and the maximum number of times a penguin can jump off this piece before it disappears (−10 000 ≤ xi, yi ≤ 10 000, 0 ≤ ni ≤ 10, 1 ≤ mi ≤ 200).

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with the integer N (1 ≤ N ≤ 100) and a floating-point number D (0 ≤ D ≤ 100 000), denoting the number of ice pieces and the maximum distance a penguin can jump.

N lines, each line containing xi, yi, ni and mi, denoting for each ice piece its X and Y coordinate, the number of penguins on it and the maximum number of times a penguin can jump off this piece before it disappears (−10 000 ≤ xi, yi ≤ 10 000, 0 ≤ ni ≤ 10, 1 ≤ mi ≤ 200).

样例输入:

2
5 3.5
1 1 1 1
2 3 0 1
3 5 1 1
5 1 1 1
5 4 0 1
3 1.1
-1 0 5 10
0 0 3 9
2 0 1 1

样例输出:

1 2 4
-1


经典的拆点流量限制法,每个ice floes拆成i和i’,i到i’的流量上限为跳的次数,然后如果能从i跳到j连一条i’到j的边(流量无穷大)
枚举dest

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <string.h>
using namespace std;
const int SIZE = 220;
const int INF = 100000000;
const int MAX_LEV=10000000;
const double EQ = 1e-9;
const int LEN = 100000;
bool used[SIZE];
int lev[SIZE];
int cap[SIZE][SIZE];
int old[SIZE][SIZE];
int que[LEN];
double lim;
class Pos{
public:
double x,y;
int pen ,jmp;
int in,out;
void set(){
   scanf("%lf%lf%d%d",&x,&y,&pen,&jmp);
   in=out=0;
}
bool near(const Pos & oth){
   double dis = sqrt((x-oth.x)*(x-oth.x) + (y-oth.y)*(y-oth.y));
   return (fabs(dis-lim)<EQ || dis<lim);
}
};
Pos dat[SIZE];
vector<int> li[SIZE];
int n;
int sz;
int tot;
int src,dest;
void init();
vector<int> ans;
void work();
int maxflow();
void cp(int [][SIZE] , int [][SIZE]);
void mklev();
int dfs(int,int);
void show();
int main(){
int cas;
scanf("%d",&cas);
while (cas--){
   init();
   work();
}
return 0;
}
void work(){
int i;
ans.clear();
cp(old,cap);
for (i=0;i<sz;i++){
   cp(cap,old);
   dest=dat[i].in;
   if (maxflow()==tot){
    //printf("arr in dat : %d\n",i);
    ans.push_back(i);
   }
}
int len=ans.size();
if (len){
   printf("%d",ans[0]);
   for (i=1;i<len;i++){
    printf(" %d",ans[i]);
   }
   printf("\n");
}else{
   printf("-1\n");
}
}
void init(){
scanf("%d%lf",&sz,&lim);
int i;
for (i=0;i<sz;i++){
   dat[i].set();
}
for (i=0;i<sz;i++){
   li[i].clear();
}
int j;
for (i=0;i<sz;i++) 
   for (j=0;j<sz;j++){
    if (i!=j && dat[i].near(dat[j])){
     li[i].push_back(j);
    }
   }
src=0;
n=1;
tot=0;
for (i=0;i<sz;i++){
   dat[i].in=n++;
   dat[i].out=n++;
}
memset(cap,0,sizeof(cap));
for (i=0;i<sz;i++){
   cap[src][dat[i].in]=dat[i].pen;
   tot+=dat[i].pen;
   cap[dat[i].in][dat[i].out]=dat[i].jmp;
}
for (i=0;i<sz;i++){
   int len = li[i].size();
   for (j=0;j<len;j++){
    int nx = li[i][j];
    cap[dat[i].out][dat[nx].in]=INF;
   }
}
}
void cp(int a[][SIZE] , int b[][SIZE]){ //a<---b;
int i,j;
for (i=0;i<SIZE;i++)
   for (j=0;j<SIZE;j++){
    a[i][j] = b[i][j];
   }
}
int maxflow(){
int sum=0;
while (true){
   mklev();
   if (lev[dest]==MAX_LEV)
    return sum;
   memset(used,false,sizeof(used));
   used[src]=true;
   sum+=dfs(src,INF);
}
}
void mklev(){
int i;
for (i=0;i<n;i++){
   lev[i]=MAX_LEV;
}
lev[src]=0;
int head=0,tail=1;
que[0]=src;
while (head!=tail){
    int nd = que[head];
    head=(head+1)%LEN;
    if (nd==dest){
    break;
    }
    for (i=0;i<n;i++){
    if (cap[nd][i]>0 && lev[i]>(lev[nd]+1)){
    lev[i]=(lev[nd]+1);
    que[tail]=i;
    tail=(tail+1)%LEN;
    }
    }
}
}
int dfs(int nd,int flow){
if (nd==dest){
    return flow;
}
int i;
for (i=0;i<n;i++){
    if (cap[nd][i]>0 && !used[i]&& lev[nd]+1==lev[i]){
   used[i]=true;
   int nf = flow<cap[nd][i]?flow:cap[nd][i];
   int ret = dfs(i,nf);
   if (ret>0){
   used[i]=false;
   cap[nd][i]-=ret;
   cap[i][nd]+=ret;
   return ret;
   }
    }
}
return 0;
}

 


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.