所以这道题不能直接用匈牙利算法解决,接下来

作者: 编程  发布:2019-08-30

HDU 2389 Rain on your Parade (二分图相配(Hopcroft-Carp的算法模板))

HDU 2389 Rain on your Parade / HUST 1164 4 Rain on your Parade(二分图的最大相称)

You’re giving a party in the garden of your villa by the sea. The party is a huge success, and everyone is here. It’s a warm, sunny evening, and a soothing wind sends fresh, salty air from the sea. The evening is progressing just as you had imagined. It could be the perfect end of a beautiful day. 
But nothing ever is perfect. One of your guests works in weather forecasting. He suddenly yells, “I know that breeze! It means its going to rain heavily in just a few minutes!” Your guests all wear their best dresses and really would not like to get wet, hence they stand terrified when hearing the bad news. 
You have prepared a few umbrellas which can protect a few of your guests. The umbrellas are small, and since your guests are all slightly snobbish, no guest will share an umbrella with other guests. The umbrellas are spread across your (gigantic) garden, just like your guests. To complicate matters even more, some of your guests can’t run as fast as the others. 
Can you help your guests so that as many as possible find an umbrella before it starts to pour? 

HDU 1072 Nightmare(BFS)

Rain on your Parade

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 655350/165535 K (Java/Others)
Total Submission(s): 3033 Accepted Submission(s): 952

Problem Description You’re giving a party in the garden of your villa by the sea. The party is a huge success, and everyone is here. It’s a warm, sunny evening, and a soothing wind sends fresh, salty air from the sea. The evening is progressing just as you had imagined. It could be the perfect end of a beautiful day.
But nothing ever is perfect. One of your guests works in weather forecasting. He suddenly yells, “I know that breeze! It means its going to rain heavily in just a few minutes!” Your guests all wear their best dresses and really would not like to get wet, hence they stand terrified when hearing the bad news.
You have prepared a few umbrellas which can protect a few of your guests. The umbrellas are small, and since your guests are all slightly snobbish, no guest will share an umbrella with other guests. The umbrellas are spread across your (gigantic) garden, just like your guests. To complicate matters even more, some of your guests can’t run as fast as the others.
Can you help your guests so that as many as possible find an umbrella before it starts to pour?

Given the positions and speeds of all your guests, the positions of the umbrellas, and the time until it starts to rain, find out how many of your guests can at most reach an umbrella. Two guests do not want to share an umbrella, however.

Input The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line containing the time t in minutes until it will start to rain (1 <=t <= 5). The next line contains the number of guests m (1 <= m <= 3000), followed by m lines containing x- and y-coordinates as well as the speed si in units per minute (1 <= si <= 3000) of the guest as integers, separated by spaces. After the guests, a single line contains n (1 <= n <= 3000), the number of umbrellas, followed by n lines containing the integer coordinates of each umbrella, separated by a space.
The absolute value of all coordinates is less than 10000.

Output For each test case, write a line containing “Scenario #i:”, where i is the number of the test case starting at 1. Then, write a single line that contains the number of guests that can at most reach an umbrella before it starts to rain. Terminate every test case with a blank line.

Sample Input

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

Sample Output

Scenario #1:
2

Scenario #2:
2

Source HDU 二零一零-10 Public Contest 题意:第一行案例数,每一种案例第一行 代表还应该有稍稍单位时间开头普降,然后是 N个访客,接下去N行是 各样访客的岗位(一维坐标平面内)和她的位移速度,接下去M行 代表雨伞数目,接下去M行表示种种雨伞的职位,问在降水前 最多有微微人能够获得雨伞(四人不可能共用一把伞)。
深入分析:以在加以的日子内 人能达到伞的地点建边,二分最大相称,即使一向用特出匈牙利(Hungary)算法一定分超时的,可用Hopcroft-Karp算法(O(sqrt(n)*edgnum)). 546MS AC。

#include
#include
#include
#include
using namespace std;
const int N = 3005;
const int INF=1<<28;

int head[N],to[N*N],next1[N*N],tot;  //存图
int dx[N],dy[N],dis;                 //左边部分距离,右边部分距离,记录右边部分没有被匹配过的点的最大距离
int machx[N],nx,machy[N];            //左边部分点匹配右边点,左边部分的点个数,右边部分点匹配左边的点
bool vist[N];

void addEdg(int u,int v){
    to[tot]=v; next1[tot]=head[u]; head[u]=tot  ;
}
bool searchpath(){//找有没有增广路
    queueq;
    dis=INF;
    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));

    for(int i=1; i<=nx; i  )
        if(machx[i]==-1)
        q.push(i),dx[i]=0;

    while(!q.empty()){
        int u=q.front(); q.pop();
        if(dx[u]>dis)
            break;
        for(int i=head[u]; i!=-1; i=next1[i]){
            int v=to[i];
            if(dy[v]==-1){
                dy[v]=dx[u] 1;
                if(machy[v]==-1)
                    dis=dy[v];
                else{
                    dx[machy[v]]=dy[v] 1;
                    q.push(machy[v]);
                }
            }
        }
    }
    return dis!=INF;
}
bool findroad(int u){
    for(int i=head[u]; i!=-1; i=next1[i]){
        int v=to[i];
        if(!vist[v]&&dy[v]==dx[u] 1){
            vist[v]=1;
            if(machy[v]!=-1&&dy[v]==dis)
                continue;
            if(machy[v]==-1||findroad(machy[v])){
                machy[v]=u; machx[u]=v;  return true;
            }
        }
    }
    return false;
}
int MaxMatch(){
    int ans=0;
    memset(machx,-1,sizeof(machx));
    memset(machy,-1,sizeof(machy));
    while( searchpath() ){
        memset(vist,0,sizeof(vist));
        for(int i=1; i<=nx; i  )
            if(machx[i]==-1)
            ans =findroad(i);
    }
    return ans;
}
//-------------上面部分的代码为模板---------------------

struct node{
    int x,y;
    double dis;
}man[N],umb[N];

double countDis(int u,int v){
    return sqrt((man[u].x-umb[v].x)*(man[u].x-umb[v].x)*1.0 (man[u].y-umb[v].y)*(man[u].y-umb[v].y)*1.0);
}
int main(){
    int T,ny,tim,c=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&tim,&nx);
        for(int i=1;i<=nx;i  ){
            scanf("%d%d%lf",&man[i].x,&man[i].y,&man[i].dis);
            man[i].dis*=tim;
        }
        scanf("%d",&ny);
        for(int i=1;i<=ny;i  )
            scanf("%d%d",&umb[i].x,&umb[i].y);

//---------------------建图---------------------
        tot=0;
        memset(head,-1,sizeof(head));
        for(int u=1;u<=nx;u  )
            for(int v=1;v<=ny;v  )
            if(man[u].dis>=countDis(u,v))
                addEdg(u,v);
//----------------------------------------------
        int ans=MaxMatch();
        printf("Scenario #%d:n%dnn",  c,ans);
    }
    return 0;
}

2389 Rain on your Parade (二分图相配(Hopcroft-Carp的算法模板)) Rain on your Parade Time Limit: 四千/三千 MS (Java/Others) Memory Limit: 655350/165535 K (Java/...

Description

You’re giving a party in the garden of your villa by the sea. The party is a huge success, and everyone is here. It’s a warm, sunny evening, and a soothing wind sends fresh, salty air from the sea. The evening is progressing just as you had imagined. It could be the perfect end of a beautiful day.
But nothing ever is perfect. One of your guests works in weather forecasting. He suddenly yells, “I know that breeze! It means its going to rain heavily in just a few minutes!” Your guests all wear their best dresses and really would not like to get wet, hence they stand terrified when hearing the bad news.
You have prepared a few umbrellas which can protect a few of your guests. The umbrellas are small, and since your guests are all slightly snobbish, no guest will share an umbrella with other guests. The umbrellas are spread across your (gigantic) garden, just like your guests. To complicate matters even more, some of your guests can’t run as fast as the others.
Can you help your guests so that as many as possible find an umbrella before it starts to pour?

Given the positions and speeds of all your guests, the positions of the umbrellas, and the time until it starts to rain, find out how many of your guests can at most reach an umbrella. Two guests do not want to share an umbrella, however.

Given the positions and speeds of all your guests, the positions of the umbrellas, and the time until it starts to rain, find out how many of your guests can at most reach an umbrella. Two guests do not want to share an umbrella, however. 

Nightmare

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9120Accepted Submission(s): 4389

Problem Description Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x 1,y), (x-1,y), (x,y 1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.

Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.

Here are some rules:

  1. We can assume the labyrinth is a 2 array.
  2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
  3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.
  4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.
  5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
  6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to

Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth.
There are five integers which indicate the different type of area in the labyrinth:
0: The area is a wall, Ignatius should not walk on it.
1: The area contains nothing, Ignatius can walk on it.
2: Ignatius' start position, Ignatius starts his escape from this position.
3: The exit of the labyrinth, Ignatius' target position.
4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.

Output For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output

Sample Input

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

Sample Output

4 -1 13

代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct node
{
    int x,y;
    int t;
    int step;
    node(int a,int b,int c,int d):x(a),y(b),t(c),step(d) {}
    void Set(int a,int b,int c,int d)
    {
        x=a;
        y=b;
        t=c;
        step=d;
    }
};

int n,m;
int xs,ys,xe,ye;
int mat[10][10];
int vis[10][10];
int dir[4][2]= {-1,0,1,0,0,-1,0,1}; //up down left right

void bfs()
{
    memset(vis,0,sizeof(vis));
    queue<node> Q;
    node first=node(xs,ys,6,0);
    if(first.x==xe&&first.y==ye&&first.t>0)
    {
        printf("%dn",first.step);
        return;
    }
    Q.push(first);
    vis[first.x][first.y]=first.t;
    while(!Q.empty())
    {
        //printf("----------------n");
        first=Q.front();
        Q.pop();
        node next=node(0,0,0,0);
        for(int i=0; i<4; i  )
        {
            int tx=first.x dir[i][0];
            int ty=first.y dir[i][1];
            if(tx>=n||tx<0||ty>=m||ty<0)
                continue;
            if(mat[tx][ty]==0)
                continue;
            if(vis[tx][ty] 1>=vis[first.x][first.y])
                continue;
            next.Set(tx,ty,first.t-1,first.step 1);
            if(mat[tx][ty]==4)
                next.t=6;
            vis[next.x][next.y]=next.t;
            //printf("%d %d %d %dn",next.x,next.y,next.t,next.step);
            if(next.x==xe&&next.y==ye&&next.t>0)
            {
                printf("%dn",next.step);
                return;
            }
            Q.push(next);
        }
    }
    printf("-1n");
}

int main()
{
    int t;
    scanf("%d",&t);
    //printf("%dn",t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; int="" j="0;" pre="" return="" xe="i;" xs="i;" ye="j;" ys="j;"><p>
</p><p>
</p>
</n;></node></queue></cstring></cstdio>

1072 Nightmare(BFS) Nightmare Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9120Accepted Submission(s): 4389 Problem...

Input

The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line containing the time t in minutes until it will start to rain (1 <=t <= 5). The next line contains the number of guests m (1 <= m <= 3000), followed by m lines containing x- and y-coordinates as well as the speed si in units per minute (1 <= s i <= 3000) of the guest as integers, separated by spaces. After the guests, a single line contains n (1 <= n <= 3000), the number of umbrellas, followed by n lines containing the integer coordinates of each umbrella, separated by a space.
The absolute value of all coordinates is less than 10000.

InputThe input starts with a line containing a single integer, the number of test cases. 
Each test case starts with a line containing the time t in minutes until it will start to rain (1 <=t <= 5). The next line contains the number of guests m (1 <= m <= 3000), followed by m lines containing x- and y-coordinates as well as the speed si in units per minute (1 <= s i <= 3000) of the guest as integers, separated by spaces. After the guests, a single line contains n (1 <= n <= 3000), the number of umbrellas, followed by n lines containing the integer coordinates of each umbrella, separated by a space. 
The absolute value of all coordinates is less than 10000. 
OutputFor each test case, write a line containing “Scenario #i:”, where i is the number of the test case starting at 1. Then, write a single line that contains the number of guests that can at most reach an umbrella before it starts to rain. Terminate every test case with a blank line. 
Sample Input

Output

For each test case, write a line containing “Scenario #i:”, where i is the number of the test case starting at 1. Then, write a single line that contains the number of guests that can at most reach an umbrella before it starts to rain. Terminate every test case with a blank line.

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

Sample Input

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

Sample Output

Sample Output

Scenario #1:
2

Scenario #2:
2

Scenario #1:
2

Scenario #2:
2
题意:给n个人坐标速度和m个伞坐标进行匹配,转化成二分图匹配
题解:二遍循环判断是否能到达,进行匹配,匈牙利算法会tle,用Hopcroft Karp算法(暂时还不是很理解,先背下来)
参考的博客,图很清楚但是注释有点少http://www.cnblogs.com/penseur/archive/2013/06/16/3138981.html

Http

HDU:
HUSTT:

图片 1图片 2

Source

二分图的最大相配

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007

using namespace std;

const int N=3000 5,maxn=100000 5,inf=0x3f3f3f3f;

struct edge{
   int x,y,v;
}g[N],u[N];

int n,m,dis;
bool used[N],ok[N][N];
int mx[N],my[N];//mx保存右侧匹配点,my保存左侧匹配点
int dx[N],dy[N];

double road(edge a,edge b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) (a.y-b.y)*(a.y-b.y));
}
bool searchP()//寻找增广路径集
{
    queue<int>q;
    dis=inf;
    memset(dy,-1,sizeof dy);
    memset(dx,-1,sizeof dx);
    for(int i=1;i<=n;i  )
        if(mx[i]==-1)//将未访问过的左侧点加入队列
        {
            q.push(i);
            dx[i]=0;//距离设为0
        }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(dx[u]>dis)break;
        for(int i=1;i<=m;i  )//取左侧点匹配到右侧
        {
            if(ok[u][i]&&dy[i]==-1)//右侧点联通且未访问
            {
                dy[i]=dx[u] 1;//i对应距离为u对应距离 1
                if(my[i]==-1)dis=dy[i];//i无匹配点
                else
                {
                    dx[my[i]]=dy[i] 1;
                    q.push(my[i]);
                }
            }
        }
    }
    return dis!=inf;
}
bool dfs(int x)
{
    for(int i=1;i<=m;i  )
    {
        if(!used[i]&&ok[x][i]&&dy[i]==dx[x] 1)//没有访问过且距上一点为1
        {
            used[i]=1;
            if(my[i]!=-1&&dy[i]==dis)continue;
            if(my[i]==-1||dfs(my[i]))
            {
                my[i]=x;
                mx[x]=i;
                return 1;
            }
        }
    }
    return 0;
}
int solve()
{
    int ans=0;
    memset(mx,-1,sizeof mx);
    memset(my,-1,sizeof my);
    while(searchP()){
        memset(used,0,sizeof used);
        for(int i=1;i<=n;i  )
            if(mx[i]==-1&&dfs(i))
              ans  ;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t,time;
    cin>>t;
    for(int k=1;k<=t;k  )
    {
        cin>>time>>n;
        for(int i=1;i<=n;i  )cin>>g[i].x>>g[i].y>>g[i].v;
        cin>>m;
        for(int i=1;i<=m;i  )cin>>u[i].x>>u[i].y;
        for(int i=1;i<=n;i  )
        {
            for(int j=1;j<=m;j  )
            {
                if(time*g[i].v>=road(g[i],u[j]))ok[i][j]=1;
                else ok[i][j]=0;
            }
        }
        cout<<"Scenario #"<<k<<":"<<endl<<solve()<<endl<<endl;
    }
    return 0;
}

难点大体

现今登时要降水了,给出n个人和m把雨伞的坐标地方,以及种种人的跑步速度,还会有距离降水的时日。每把雨伞只可以供一位选用。求在降雨前最多有多少人得以得到雨伞。

View Code

化解思路

其一标题一看就是二分图的最大相配难点。但若直接把匈牙利(Hungary)算法往上一摆,会TLE。

干什么呢?好赏心悦目题:n,m<=贰仟。而本来大家做的难题都是n,m<=100或<=200的。所以那道题无法直接用匈牙利(Magyarország)算法化解。

所以那道题咱们要用到匈牙利(Hungary)算法的立异版:Hopcroft-Karp算法(一下简称HK算法)

小编们知道,匈牙利(Magyarország)算法时间效能不高的因由正是在一回相称时只走一条增广边,每一次都要重新找增广边,所以时间效用低。

这就是说,HK算法便是在每贰回判别前,先用多个bfs预管理管理出多条增广边,上边先交给代码。

代码中的变量表明:
Dist:七个全局变量,保存当前最长的增广路的深浅,方便及时脱离bfs,同有的时候间也造福后边再拓宽Hungary时即时退出(前面会讲到)
Deep_x:人相应的点的深度(也正是到此点时的增广路长度),同期能够方便决断人i是或不是在此番bfs中度过了。这些变量在匈牙利(Hungary)算法中也会用到(后边会提起)
Deep_y:伞对应的点的纵深(同上),也能判定伞是不是在本次bfs中是或不是用过
Match_x:人所相称的伞的号码
Match_y:伞所相称的人的数码
E:从人->伞的边
其它变量的含义与主题素材一致

bool bfs()
{
    queue<int> Q;//bfs要用的队列
    while (!Q.empty())
        Q.pop();
    Dist=inf;//先置为inf
    mem(Deep_x,-1);//先置为-1,表示还未经过
    mem(Deep_y,-1);
    for (int i=1;i<=m;i  )
        if (Match_x[i]==-1)//若人i还未匹配,则将其加入队列(因为增广路的开始点是未匹配点)
        {
            Deep_x[i]=0;
            Q.push(i);
        }
    while (!Q.empty())//因为有可能所有人都已经匹配,所以要把while判断写前面,以免出现RE
    {
        int u=Q.front();
        Q.pop();
        if (Deep_x[u]>Dist)//若发现当前选出的人u的深度已经大于能形成增广路的最大深度了,直接退出。这是一个很好的剪枝
            break;
        for (int i=0;i<E[u].size();i  )
        {
            int v=E[u][i];//选择伞v
            if (Deep_y[v]==-1)//若伞v在这一次bfs中还未走过
            {
                Deep_y[v]=Deep_x[u] 1;//首先更新伞v的深度,同时表示已经处理过伞v了
                if (Match_y[v]==-1)//当伞v还未匹配时,说明找到了一条增广路,这时更新最长增广路的值Dist。因为是bfs,所以可以保证越在后面出来的Deep值越大,所以不用加max
                {
                    Dist=Deep_y[v];
                }
                else//如果伞v已经匹配,则处理其对应的匹配的人,并将这个人加入队列
                {
                    Deep_x[Match_y[v]]=Deep_y[v] 1;
                    Q.push(Match_y[v]);
                }
            }
        }
    }
    //cout<<"Dist "<<Dist<<endl;
    if (Dist==inf)//这表示没有增广路了,说明算法执行完毕,返回0
        return 0;
    return 1;
}

总结一下,那些bfs进度的含义正是增广多条增广路,方便前边匈牙利算法。

那便是说接下去正是修改匈牙利(Magyarország)算法了。依然先付给代码。

bool Hungary(int u)
{
    for (int i=0;i<E[u].size();i  )
    {
        int v=E[u][i];
        if ((vis[v]==0)&&(Deep_x[u] 1==Deep_y[v]))//注意,这里用到了bfs计算出来的Deep数组,这可以用来判断当前选的伞v是否是我们在dfs中选的那条增广路,有效剪枝
        {
            vis[v]=1;
            if ((Match_y[v]!=-1)&&(Deep_y[v]==Dist))//若发现当前伞v的Deep已经和最大增广路长度一样,并且伞v已匹配,那么再递归向下找是无意义的,直接continue
                continue;
            if ((Match_y[v]==-1)||(Hungary(Match_y[v])))
            {
                Match_x[u]=v;//注意,因为添加了人对应匹配的伞这个变量,所以也要更新(这在之前的匈牙利中是没有的)
                Match_y[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

最终一共一下HK算法的入眼流程正是:
先寻找多条不相交的增广路。
用匈牙利(Magyarország)算法举行相配。

(如有不科学之处还请各路神犇指教)

 

代码(前面附上了TLE的纯匈牙利(Hungary)算法)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=4000;
const int inf=2147483647;

int n,m;
int Time;//距离下雨的时间
int Dist;//下面这些变量的意义在上文已经讲过啦
vector<int> E[maxN];
int Match_x[maxN];
int Match_y[maxN];
bool vis[maxN];
int Deep_x[maxN];
int Deep_y[maxN];
int X[maxN];//人的X坐标
int Y[maxN];
int Speed[maxN];//人的速度

int read();
bool Judge(int u,int v,int num);
bool bfs();
bool Hungary(int u);

int main()
{
    int T;
    T=read();
    for (int ti=1;ti<=T;ti  )
    {
        Time=read();
        m=read();
        for (int i=1;i<=m;i  )
            E[i].clear();
        for (int i=1;i<=m;i  )
        {
            X[i]=read();
            Y[i]=read();
            Speed[i]=read();
        }
        n=read();
        for (int i=1;i<=n;i  )
        {
            int x,y;
            x=read();
            y=read();
            for (int j=1;j<=m;j  )
                if (Judge(x,y,j))
                {
                    E[j].push_back(i);
                }
        }
        int Ans=0;
        mem(Match_x,-1);
        mem(Match_y,-1);
        while (bfs())//HK算法
        {
            mem(vis,0);
            for (int i=1;i<=m;i  )
                if (Match_x[i]==-1)
                    if (Hungary(i))
                        Ans  ;
        }
        printf("Scenario #%d:n%dnn",ti,Ans);
    }
    return 0;
}

int read()//读入优化
{
    int x=0;
    int k=1;
    char ch=getchar();
    while (((ch<'0')||(ch>'9'))&&(ch!='-'))
        ch=getchar();
    if (ch=='-')
    {
        k=-1;
        ch=getchar();
    }
    while ((ch<='9')&&(ch>='0'))
    {
        x=x*10 ch-48;
        ch=getchar();
    }
    return x*k;
}

bool Judge(int u,int v,int num)//判断某个人是否可以跑到某把伞
{
    long long Dist=(long long)((X[num]-u))*(X[num]-u) (long long)((Y[num]-v))*(Y[num]-v);
    long long D=(long long)(Time)*Speed[num];
    if (D*D>=Dist)
        return 1;
    return 0;
}

bool bfs()
{
    queue<int> Q;//bfs要用的队列
    while (!Q.empty())
        Q.pop();
    Dist=inf;//先置为inf
    mem(Deep_x,-1);//先置为-1,表示还未经过
    mem(Deep_y,-1);
    for (int i=1;i<=m;i  )
        if (Match_x[i]==-1)//若人i还未匹配,则将其加入队列(因为增广路的开始点是未匹配点)
        {
            Deep_x[i]=0;
            Q.push(i);
        }
    while (!Q.empty())//因为有可能所有人都已经匹配,所以要把while判断写前面,以免出现RE
    {
        int u=Q.front();
        Q.pop();
        if (Deep_x[u]>Dist)//若发现当前选出的人u的深度已经大于能形成增广路的最大深度了,直接退出。这是一个很好的剪枝
            break;
        for (int i=0;i<E[u].size();i  )
        {
            int v=E[u][i];//选择伞v
            if (Deep_y[v]==-1)//若伞v在这一次bfs中还未走过
            {
                Deep_y[v]=Deep_x[u] 1;//首先更新伞v的深度,同时表示已经处理过伞v了
                if (Match_y[v]==-1)//当伞v还未匹配时,说明找到了一条增广路,这时更新最长增广路的值Dist。因为是bfs,所以可以保证越在后面出来的Deep值越大,所以不用加max
                {
                    Dist=Deep_y[v];
                }
                else//如果伞v已经匹配,则处理其对应的匹配的人,并将这个人加入队列
                {
                    Deep_x[Match_y[v]]=Deep_y[v] 1;
                    Q.push(Match_y[v]);
                }
            }
        }
    }
    //cout<<"Dist "<<Dist<<endl;
    if (Dist==inf)//这表示没有增广路了,说明算法执行完毕,返回0
        return 0;
    return 1;
}

bool Hungary(int u)
{
    for (int i=0;i<E[u].size();i  )
    {
        int v=E[u][i];
        if ((vis[v]==0)&&(Deep_x[u] 1==Deep_y[v]))//注意,这里用到了bfs计算出来的Deep数组,这可以用来判断当前选的伞v是否是我们在dfs中选的那条增广路,有效剪枝
        {
            vis[v]=1;
            if ((Match_y[v]!=-1)&&(Deep_y[v]==Dist))//若发现当前伞v的Deep已经和最大增广路长度一样,并且伞v已匹配,那么再递归向下找是无意义的,直接continue
                continue;
            if ((Match_y[v]==-1)||(Hungary(Match_y[v])))
            {
                Match_x[u]=v;//注意,因为添加了人对应匹配的伞这个变量,所以也要更新(这在之前的匈牙利中是没有的)
                Match_y[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
/* 匈牙利算法,TLE
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int maxN=4000;
const int inf=2147483647;

int n,m;
vector<int> E[maxN];
bool vis[maxN];
int Match[maxN];
int GuestX[maxN];
int GuestY[maxN];
int Speed[maxN];

int read();
bool Hungary(int u);

int main()
{
    int T;
    int Time;
    cin>>T;
    for (int ti=1;ti<=T;ti  )
    {
        cin>>Time;
        cin>>m;
        for (int i=1;i<=m;i  )
            E[i].clear();
        for (int i=1;i<=m;i  )
        {
            GuestX[i]=read();
            GuestY[i]=read();
            Speed[i]=read();
            Speed[i]=Speed[i]*Time;
        }
        int x,y;
        cin>>n;
        for (int i=1;i<=n;i  )
        {
            x=read();
            y=read();
            for (int j=1;j<=m;j  )
            {
                int Dist=(x-GuestX[j])*(x-GuestX[j]) (y-GuestY[j])*(y-GuestY[j]);
                if (Speed[i]*Speed[i]>=Dist)
                    E[j].push_back(i);
            }
        }
        int Ans=0;
        memset(Match,-1,sizeof(Match));
        for (int i=1;i<=m;i  )
        {
            memset(vis,0,sizeof(vis));
            if (Hungary(i))
            {
                Ans  ;
            }
        }
        printf("Scenario #%d:n%dnn",ti,Ans);
        //cout<<Ans<<endl;
    }
}

int read()
{
    int x=0;
    int k=1;
    char ch=getchar();
    while (((ch<'0')||(ch>'9'))&&(ch!='-'))
        ch=getchar();
    if (ch=='-')
    {
        k=-1;
        ch=getchar();
    }
    while ((ch<='9')&&(ch>='0'))
    {
        x=x*10 ch-48;
        ch=getchar();
    }
    return x*k;
}

bool Hungary(int u)
{
    for (int i=0;i<E[u].size();i  )
    {
        int v=E[u][i];
        if (vis[v]==0)
        {
            vis[v]=1;
            if ((Match[v]==-1)||(Hungary(Match[v])))
            {
                Match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
*/

本文由9159.com发布于编程,转载请注明出处:所以这道题不能直接用匈牙利算法解决,接下来

关键词: 9159.com