![[kuangbin带你飞]专题十一 网络流](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[kuangbin带你飞]专题十一 网络流")
|
ID
|
Origin
|
Title
|
||
|---|---|---|---|---|
| 34 / 81 | Problem A | POJ 3436 | ACM Computer Factory | |
| 92 / 195 | Problem B | POJ 3281 | Dining | |
| 55 / 148 | Problem C | POJ 1087 | A Plug for UNIX | |
| 59 / 111 | Problem D | POJ 2195 | Going Home | |
| 44 / 132 | Problem E | POJ 2516 | Minimum Cost | |
| 35 / 72 | Problem F | POJ 1459 | Power Network | |
| 40 / 217 | Problem G | HDU 4280 | Island Transport | |
| 42 / 133 | Problem H | HDU 4292 | Food | |
| 34 / 90 | Problem I | HDU 4289 | Control | |
| 28 / 90 | Problem J | UVA 10480 | Sabotage | |
| 19 / 37 | Problem K | HDU 2732 | Leapin' Lizards | |
| 13 / 136 | Problem L | HDU 3338 | Kakuro Extension | |
| 36 / 358 | Problem M | HDU 3605 | Escape | |
| 17 / 58 | Problem N | HDU 3081 | Marriage Match II | |
| 15 / 61 | Problem O | HDU 3416 | Marriage Match IV |
34 / 81 Problem A POJ 3436 ACM Computer Factory
没懂。。
此题是最大流问题。题目意思比较难懂。
看得比较纠结。
就是说有N台组装电脑的机器。电脑的组成部分共有P部分。
每台机器有P个输入输出规格。还有一个容量Q；
其中输入规格有三种情况：0,1,2
0：该部分不能存在
1：该部分必须保留
2：该部分可有可无
输出规格有2种情况：0,1
0：该部分不存在
1：该部分存在
要求的是生产电脑最大的台数，就是求网络中的最大流。
这相当于是生产线。需要自己去建图。
但是考虑到每台机器都有容量，所以把一台机器分成两个点，中间建一条容量的边。
同时如果一台机器的输出符合另一台机器的输入，则建一条容量无穷大的边。
同时要增加源点和汇点。输入没有1的连接源点，输出全部是1的连接汇点。
92 / 195 Problem B POJ 3281 Dining
本题能够想到用最大流做，那真的是太绝了。建模的方法很妙！
题意就是有N头牛，F个食物，D个饮料。
N头牛每头牛有一定的喜好，只喜欢几个食物和饮料。
每个食物和饮料只能给一头牛。一头牛只能得到一个食物和饮料。
而且一头牛必须同时获得一个食物和一个饮料才能满足。问至多有多少头牛可以获得满足。
最初相当的是二分匹配。但是明显不行，因为要分配两个东西，两个东西还要同时满足。
最大流建图是把食物和饮料放在两端。一头牛拆分成两个点，两点之间的容量为1.喜欢的食物和饮料跟牛建条边，容量为1.
加个源点和汇点。源点与食物、饮料和汇点的边容量都是1，表示每种食物和饮料只有一个。
这样话完全是最大流问题了，。
/*
POJ 3281 最大流
//源点-->food-->牛(左)-->牛(右)-->drink-->汇点
//精髓就在这里，牛拆点，确保一头牛就选一套food和drink的搭配 */ #include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std; //****************************************************
//最大流模板
//初始化：g[][],start,end
//******************************************************
const int MAXN=;
const int INF=0x3fffffff;
int g[MAXN][MAXN];//存边的容量，没有边的初始化为0
int path[MAXN],flow[MAXN],start,end;
int n;//点的个数，编号0-n.n包括了源点和汇点。 queue<int>q;
int bfs()
{
int i,t;
while(!q.empty())q.pop();//把清空队列
memset(path,-,sizeof(path));//每次搜索前都把路径初始化成-1
path[start]=;
flow[start]=INF;//源点可以有无穷的流流进
q.push(start);
while(!q.empty())
{
t=q.front();
q.pop();
if(t==end)break;
//枚举所有的点，如果点的编号起始点有变化可以改这里
for(i=;i<=n;i++)
{
if(i!=start&&path[i]==-&&g[t][i])
{
flow[i]=flow[t]<g[t][i]?flow[t]:g[t][i];
q.push(i);
path[i]=t;
}
}
}
if(path[end]==-)return -;//即找不到汇点上去了。找不到增广路径了
return flow[end];
}
int Edmonds_Karp()
{
int max_flow=;
int step,now,pre;
while((step=bfs())!=-)
{
max_flow+=step;
now=end;
while(now!=start)
{
pre=path[now];
g[pre][now]-=step;
g[now][pre]+=step;
now=pre;
}
}
return max_flow;
}
int main()
{
int N,F,D;
while(scanf("%d%d%d",&N,&F,&D)!=EOF)
{
memset(g,,sizeof(g));
n=F+D+*N+;
start=;
end=n;
for(int i=;i<=F;i++)g[][i]=;
for(int i=F+*N+;i<=F+*N+D;i++)g[i][n]=;
for(int i=;i<=N;i++)g[F+*i-][F+*i]=;
int k1,k2;
int u;
for(int i=;i<=N;i++)
{
scanf("%d%d",&k1,&k2);
while(k1--)
{
scanf("%d",&u);
g[u][F+*i-]=;
}
while(k2--)
{
scanf("%d",&u);
g[F+*i][F+*N+u]=;
}
}
printf("%d\n",Edmonds_Karp());
}
return ;
}
55 / 148 Problem C POJ 1087 A Plug for UNIX
题意：在一个房间里有N种插座和使用M种插座的电器，，这M种插座有些在现有的插座中不包含，不过可以通过适配器来转化，有K种类型的适配器来转化，让你求最少会有多少电器没法使用插座。
思路:最大二分匹配。即求出最多有多少电器有相应的插座，然后用M减去就是所求，不过建图有点难想，我也是看了别人的解题报告才明白的。将电器和相应的插座类型连接起来，将能相互转化的插座连接起来，然后将不能直接使用N种插座而通过适配器的转换就能用的电器和插座连起来，然后就是求M种电器和Ｎ种插座的最大匹配了。呃，其实看到很多博客都是用最大流做的，原本这题也是在最大流的练习中找到的，但是我发现最大匹配更好理解，而且二分匹配加上源点和汇点就能转化成最大流。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#define N 505
using namespace std ; map<string , int>p ;
int mp[N][N] ;
int n , m , k , nx ;
int f[N] , d[N] ; int dfs( int x )
{
int i ; for ( i = m + ; i <= m + nx ; i++ )
{
if ( !f[i] && mp[x][i] )
{
f[i] = ;
if ( !d[i] || dfs( d[i] ))
{
d[i] = x ;
return ;
}
}
}
return ;
}
//二分匹配模板
int floyd( )
{
int i , sum ;
sum = ;
memset( d , , sizeof ( d ));
for ( i = ; i <= m ; i++ )
{
memset( f , , sizeof ( f ));
if ( dfs( i ))
sum++;
}
return sum ;
} int main()
{
int i , j , t ;
string str1 , str2 ; //freopen("input.txt" , "r" , stdin );
//输入N种插座
scanf ( "%d" , &n ) ;
p.clear();
nx = n ;
for ( i = ; i <= n ; i++ )
{
cin>>str1 ;
p[str1] = i ;
} //输入M种电器
scanf ( "%d" , &m );
for ( i = ; i <= m ; i++ )
{
cin>>str1>>str2 ;
if ( p[str2] != )
{
int x = p[str2] ;
mp[i][x+m] = ;
}
else
{
n++ ;
p[str2] = n ;
mp[i][n+m] = ;
}
} //输入K种转化关系
scanf ( "%d" , &k );
for ( i = ; i <= k ; i++ )
{
cin>>str1>>str2 ;
if ( p[str1] == )
{
n++ ;
p[str1] = n ;
}
if ( p[str2] == )
{
n++ ;
p[str2] = n ;
}
mp[p[str1]+m][p[str2]+m] = ;
} //将通过适配器可以使用原来N种插座的电器连起来。
for ( i = ; i <= m + n ; i++ )
for ( j = ; j <= m + n ; j++ )
for ( t = ; t <= m + n ; t++ )
if ( mp[j][i] && mp[i][t] && !mp[j][t] )
mp[j][t] = ; int flow = floyd( );
printf ( "%d\n" , m - flow ) ;
return ;
}
最大流代码
#include<stdio.h>
#include<map>
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
using namespace std; //****************************************************
//最大流模板
//初始化：g[][],start,end
//******************************************************
const int MAXN=;
const int INF=0x3fffffff;
int g[MAXN][MAXN];//存边的容量，没有边的初始化为0
int path[MAXN],flow[MAXN],start,end;
int n;//点的个数，编号0-n.n包括了源点和汇点。 queue<int>q;
int bfs()
{
int i,t;
while(!q.empty())q.pop();//把清空队列
memset(path,-,sizeof(path));//每次搜索前都把路径初始化成-1
path[start]=;
flow[start]=INF;//源点可以有无穷的流流进
q.push(start);
while(!q.empty())
{
t=q.front();
q.pop();
if(t==end)break;
//枚举所有的点，如果点的编号起始点有变化可以改这里
for(i=;i<=n;i++)
{
if(i!=start&&path[i]==-&&g[t][i])
{
flow[i]=flow[t]<g[t][i]?flow[t]:g[t][i];
q.push(i);
path[i]=t;
}
}
}
if(path[end]==-)return -;//即找不到汇点上去了。找不到增广路径了
return flow[end];
}
int Edmonds_Karp()
{
int max_flow=;
int step,now,pre;
while((step=bfs())!=-)
{
max_flow+=step;
now=end;
while(now!=start)
{
pre=path[now];
g[pre][now]-=step;
g[now][pre]+=step;
now=pre;
}
}
return max_flow;
} map<string,int>hash;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
string str1,str2;
int N,M;
int tol;
while(scanf("%d",&N)!=EOF)
{
hash.clear();
memset(g,,sizeof(g));
start=;
end=;
tol=;
while(N--)
{
cin>>str1;
hash[str1]=tol;
g[][tol]=;
tol++;
}
scanf("%d",&M);
for(int i=;i<M;i++)
{
cin>>str1>>str2;
if(hash[str1]==)hash[str1]=tol++;
if(hash[str2]==)hash[str2]=tol++;
g[hash[str1]][end]=;
g[hash[str2]][hash[str1]]=;
}
scanf("%d",&N);
while(N--)
{
cin>>str1>>str2;
if(hash[str1]==)hash[str1]=tol++;
if(hash[str2]==)hash[str2]=tol++;
g[hash[str2]][hash[str1]]=INF;
}
n=tol-;
printf("%d\n",M-Edmonds_Karp()); }
return ;
}
59 / 111 Problem D POJ 2195 Going Home
hint.做过的题，解题报告见以前博客
44 / 132 Problem E POJ 2516 Minimum Cost
hint.做过的题，解题报告见以前博客
35 / 72 Problem F POJ 1459 Power Network
hint.做过的题，解题报告见以前博客
40 / 217 Problem G HDU 4280 Island Transport
题意：有N个岛屿之间有M双向条路，每条路每个小时最多能通过C个人，现在问一个小时内，最多能把多少个顾客从最西边的岛屿送至最东边的岛屿上。
思路：网络流，求最大流。建图：每条路连接的两个岛屿之间建立一条容量为C的双向边，取超级源点与汇点，源点与最西边的岛屿，汇点与最东边的岛屿建立一条流量为无穷大的边。
/*
最大流模板
sap
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std; const int MAXN=;//点数的最大值
const int MAXM=;//边数的最大值
const int INF=0x3f3f3f3f; struct Node
{
int from,to,next;
int cap;
}edge[MAXM];
int tol;
int head[MAXN];
int dep[MAXN];
int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y int n;//n是总的点的个数，包括源点和汇点 void init()
{
tol=;
memset(head,-,sizeof(head));
} void addedge(int u,int v,int w)
{
edge[tol].from=u;
edge[tol].to=v;
edge[tol].cap=w;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].from=v;
edge[tol].to=u;
edge[tol].cap=;
edge[tol].next=head[v];
head[v]=tol++;
}
void BFS(int start,int end)
{
memset(dep,-,sizeof(dep));
memset(gap,,sizeof(gap));
gap[]=;
int que[MAXN];
int front,rear;
front=rear=;
dep[end]=;
que[rear++]=end;
while(front!=rear)
{
int u=que[front++];
if(front==MAXN)front=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]!=-)continue;
que[rear++]=v;
if(rear==MAXN)rear=;
dep[v]=dep[u]+;
++gap[dep[v]];
}
}
}
int SAP(int start,int end)
{
int res=;
BFS(start,end);
int cur[MAXN];
int S[MAXN];
int top=;
memcpy(cur,head,sizeof(head));
int u=start;
int i;
while(dep[start]<n)
{
if(u==end)
{
int temp=INF;
int inser;
for(i=;i<top;i++)
if(temp>edge[S[i]].cap)
{
temp=edge[S[i]].cap;
inser=i;
}
for(i=;i<top;i++)
{
edge[S[i]].cap-=temp;
edge[S[i]^].cap+=temp;
}
res+=temp;
top=inser;
u=edge[S[top]].from;
}
if(u!=end&&gap[dep[u]-]==)//出现断层，无增广路
break;
for(i=cur[u];i!=-;i=edge[i].next)
if(edge[i].cap!=&&dep[u]==dep[edge[i].to]+)
break;
if(i!=-)
{
cur[u]=i;
S[top++]=i;
u=edge[i].to;
}
else
{
int min=n;
for(i=head[u];i!=-;i=edge[i].next)
{
if(edge[i].cap==)continue;
if(min>dep[edge[i].to])
{
min=dep[edge[i].to];
cur[u]=i;
}
}
--gap[dep[u]];
dep[u]=min+;
++gap[dep[u]];
if(u!=start)u=edge[S[--top]].from;
}
}
return res;
} int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int start,end;
int m;
int u,v,z;
int T;
scanf("%d",&T); while(T--)
{
init();
scanf("%d%d",&n,&m);
int minx=;
int maxx=-;
int x,y;
for(int i=;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(minx>x)
{
minx=x;
start=i;
}
if(maxx<x)
{
maxx=x;
end=i;
}
} while(m--)
{
scanf("%d%d%d",&u,&v,&z);
addedge(u,v,z);
addedge(v,u,z);
}
//n一定是点的总数，这是使用SAP模板需要注意的
int ans=SAP(start,end);
printf("%d\n",ans);
}
return ;
}
42 / 133 Problem H HDU 4292 Food
题意：有F种食物 D种饮料 它们都有一定的数量 有N个人 每个人都有自己喜欢吃的食物和饮料 （每个人至少要一种食物和饮料） 只有能满足他的要求时他才会接服务 求最大能满足多少人？
思路：网络流 建一超级源点 汇点 源点与食物相连 边权为其数量，汇点与饮料相连 边权也为其数量 把人分成两个点 之间的边权为1 每个人与之需要的食物和饮料相连 边权为1
/*
题意：F种食物和D种饮料，每种食物和饮料的数目也是固定的，总共有N位顾客，每位顾客都只吃喝固定种类的食品
饮料，问最多能满足多少为顾客。 题解：最大流+拆点；
建图：将每位顾客拆成两个点，同一顾客之间加入权值为1的有向边限制了只能是一位一位顾客来满足，再加入源点
来连接每一种食物，权值为该食物数量，然后根据顾客喜欢的食物连接顾客，权值为1，因为每位顾客只需1份食物饮
料，然后加入饮料结点并根据顾客喜好连接，权值同样为1，然后将饮料与汇点连接，权值为饮料的数目，最终求得
的最大流即为最多能满足的顾客。
*/
#include <cstdio>
#include <cstring> #define EMAX 200000
#define VMAX 1005 const int INF = 0xfffffff; int head[VMAX],dis[VMAX],cur[VMAX],gap[VMAX],pre[VMAX];
int EN;
struct edge
{
int from,to;
int weight;
int next;
}e[EMAX]; void insert(int u,int v,int w)
{
e[EN].to = v;
e[EN].weight = w;
e[EN].next = head[u];
head[u] = EN++;
e[EN].weight = ;
e[EN].to = u;
e[EN].next = head[v];
head[v] = EN++;
} int sap(int s,int t, int n)
{
memset(dis,,sizeof(dis));
memset(gap,,sizeof(gap));
for(int i=; i<=n; i++)
cur[i] = head[i];
int u = pre[s];
pre[s] = s;
int ret = ;
int temp = -;
gap[] = n;
bool flag;
while(dis[s] < n)
{
flag = false;
for(int &i = cur[u]; i != -; i = e[i].next)
{
int v = e[i].to;
if(e[i].weight && dis[u] == dis[v] + )
{
if (temp == - || temp>e[i].weight)
temp = e[i].weight;
pre[v] = u;
u = v;
if(v == t)
{
ret += temp;
for(u = pre[u];v != s;v = u,u = pre[u])
{
e[cur[u]].weight -= temp;
e[cur[u]^].weight += temp;
}
temp = -;
}
flag = true;
break;
}
}
if (flag)
continue; int mindis = n;
for(int i = head[u]; i != - ; i = e[i].next)
{
int v = e[i].to;
if(e[i].weight && mindis > dis[v])
{
cur[u] = i;
mindis = dis[v];
}
}
gap[dis[u]]--;
if( gap[dis[u]] == )
break;
dis[u] = mindis+;
gap[dis[u]]++;
u = pre[u];
}
return ret;
} int main(void)
{
int n,f,d,t;
char s[];
while (scanf("%d%d%d",&n,&f,&d) == )
{
memset(head,-,sizeof(head));
EN = ;
for(int i=; i<=f; i++)
{
scanf("%d",&t);
insert(,i,t);//源点加边
}
for(int i=; i<=d; i++)
{
scanf("%d",&t);
insert(f+*n+i,f+*n+d+,t);//汇点加边
}
for(int i=; i<=n; i++)
insert(f+i,f+n+i,);//拆点
for(int i=; i<=n; i++)
{
scanf("%s",s+);
for(int j=; j<=f; j++)
if (s[j] == 'Y')
insert(j,f+i,);//顾客与食物加边
}
for(int i=; i<=n; i++)
{
scanf("%s",s+);
for(int j=; j<=d; j++)
if (s[j] == 'Y')
insert(f+n+i,f+*n+j,);//顾客与饮料加边
}
printf("%d\n",sap(,f+*n+d+,f+*n+d+));
}
return ;
}
34 / 90 Problem I HDU 4289 Control
成都赛区网络赛1002题。
一场网络赛两题最大流，用SAP模板可以秒掉。
//
/*
HDU 4289
G++ 62ms 1888K
最大流
SAP
*/
#include<stdio.h>
#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
using namespace std; const int MAXN=;//点数的最大值
const int MAXM=;//边数的最大值
const int INF=0x3f3f3f3f; struct Node
{
int from,to,next;
int cap;
}edge[MAXM];
int tol;
int head[MAXN];
int dep[MAXN];
int gap[MAXN];//gap[x]=y:说明残留网络中 dep[i]==x的个数为y int n;//点的实际个数，一定是总的点的个数，包括源点和汇点
void init()
{
tol=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w)
{
edge[tol].from=u;
edge[tol].to=v;
edge[tol].cap=w;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].from=v;
edge[tol].to=u;
edge[tol].cap=;
edge[tol].next=head[v];
head[v]=tol++;
}
void BFS(int start,int end)
{
memset(dep,-,sizeof(dep));
memset(gap,,sizeof(gap));
gap[]=;
int que[MAXN];
int front,rear;
front=rear=;
dep[end]=;
que[rear++]=end;
while(front!=rear)
{
int u=que[front++];
if(front==MAXN)front=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].cap!=||dep[v]!=-)continue;
que[rear++]=v;
if(rear==MAXN)rear=;
dep[v]=dep[u]+;
++gap[dep[v]];
}
}
}
int SAP(int start,int end)
{
int res=;
BFS(start,end);
int cur[MAXN];
int S[MAXN];
int top=;
memcpy(cur,head,sizeof(head));
int u=start;
int i;
while(dep[start]<n)
{
if(u==end)
{
int temp=INF;
int inser;
for(i=;i<top;i++)
if(temp>edge[S[i]].cap)
{
temp=edge[S[i]].cap;
inser=i;
}
for(i=;i<top;i++)
{
edge[S[i]].cap-=temp;
edge[S[i]^].cap+=temp;
}
res+=temp;
top=inser;
u=edge[S[top]].from;
}
if(u!=end&&gap[dep[u]-]==)//出现断层，无增广路
break;
for(i=cur[u];i!=-;i=edge[i].next)
if(edge[i].cap!=&&dep[u]==dep[edge[i].to]+)
break;
if(i!=-)
{
cur[u]=i;
S[top++]=i;
u=edge[i].to;
}
else
{
int min=n;
for(i=head[u];i!=-;i=edge[i].next)
{
if(edge[i].cap==)continue;
if(min>dep[edge[i].to])
{
min=dep[edge[i].to];
cur[u]=i;
}
}
--gap[dep[u]];
dep[u]=min+;
++gap[dep[u]];
if(u!=start)
u=edge[S[--top]].from;
} }
return res;
} int main()
{
//freopen("B.in","r",stdin);
//freopen("B.out","w",stdout);
int N,M;
int u,v;
int start;
int end;
while(scanf("%d%d",&N,&M)!=EOF)
{
init();
scanf("%d%d",&start,&end);
start=*start-;
end=*end;
n=*N;
for(int i=;i<=N;i++)
{
scanf("%d",&u);
addedge(*i-,*i,u);
addedge(*i,*i-,u);
}
while(M--)
{
scanf("%d%d",&u,&v);
addedge(*u,*v-,INF);
addedge(*v,*u-,INF);//这里一定要注意
}
printf("%d\n",SAP(start,end));
}
return ;
}
28 / 90 Problem J UVA 10480 Sabotage
最大流
19 / 37 Problem K HDU 2732 Leapin' Lizards
最大流
13 / 136 Problem L HDU 3338 Kakuro Extension
很神奇的最大流的题目。很有意思。
题目意思就是在n*m的格子中，有黑白两种格子。要在白格子中填入数字1~9
* 每一段横竖连续的白格子的和是知道的。
* 求出一种满足的，保证有解。
* 最大流。
* 按照横竖段进行编号。然后行进列出，构造图形。
*
* 为了保证填入的数字是1~9，所以一开始每个格子减掉了1，相应的流入和流出都减掉。
* 然后格子的边的赋值为8.
* 还有就是要记录下相应边的编号，便于输出结果。
36 / 358 Problem M HDU 3605 Escape
这题一看题目是很简单的最大流。
但是数据好大，试了很多模板，都是TLE。
后来发现可以合并点，
因为m<=10.
所以用二进制记录。
在n个点中，如果是一样的就合并。
这样最多是1024+m+2个点。
但是这题还是很坑。。。。在HDU上用G++交无论如何都是TLE的。直接读入数据输出都是TLE.
改成C++就AC了。。。
17 / 58 Problem N HDU 3081 Marriage Match II
最大流+二分+并查集
15 / 61 Problem O HDU 3416 Marriage Match IV
这题就是求从A到B的最短路径的条数。
一条边只能经过一次。
先通过最短路去除掉没有用的边。
然后用一次最大流就是答案了。
从A和B分别出发求最短路dist1,dist2.
注意从B求得额时候要反向。
如果dist1[a]+dist2[b]+c==dist1[B].那么这条边就是有用的。。
我用的SPFA求最短路的。