﻿ 所以这道题不能直接用匈牙利算法解决，接下来_9159.com

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

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）

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行表示种种雨伞的职位，问在降水前 最多有微微人能够获得雨伞（四人不可能共用一把伞）。

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

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

}
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;
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;
}
int v=to[i];
if(!vist[v]&&dy[v]==dx[u] 1){
vist[v]=1;
if(machy[v]!=-1&&dy[v]==dis)
continue;
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)
}
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;
for(int u=1;u<=nx;u  )
for(int v=1;v<=ny;v  )
if(man[u].dis>=countDis(u,v))
//----------------------------------------------
int ans=MaxMatch();
printf("Scenario #%d:n%dnn",  c,ans);
}
return 0;
}
``````

### 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;
int vis;
int dir= {-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];
int ty=first.y dir[i];
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
``````

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

``````

### Http

HDU:
HUSTT:  ### 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];

{
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  )
{
else ok[i][j]=0;
}
}
cout<<"Scenario #"<<k<<":"<<endl<<solve()<<endl<<endl;
}
return 0;
}
``````

View Code

## 化解思路

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;
}
``````

``````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的纯匈牙利（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];//人的速度

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

int main()
{
int T;
for (int ti=1;ti<=T;ti  )
{
for (int i=1;i<=m;i  )
E[i].clear();
for (int i=1;i<=m;i  )
{
}
for (int i=1;i<=n;i  )
{
int x,y;
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 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];

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  )
{
Speed[i]=Speed[i]*Time;
}
int x,y;
cin>>n;
for (int i=1;i<=n;i  )
{
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 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;
}
*/
``````