题目链接：

思路：题意真的有点难理解：在城市A->B之间通过所有路径一小时之内能通过最大的车辆(Maxflow)/所有边上通过最大车流量（cap）的那条叫做redundancy ratio。最小的redundancy ratio是前者最大的车流量的那一条（cap），问minimum redundancy ratio是多少。

其实就是跑一次最大流,每当找到一条增广路时，记录此时的cap,然后取最大的就行了。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 #define MAXN 1111  8 #define inf 1<<30  9  10 struct Edge{ 11     int v,cap,next; 12 }edge[MAXN*MAXN]; 13  14 int n,m,vs,vt,NE,NV,MAX; 15 int head[MAXN]; 16  17 void Insert(int u,int v,int cap) 18 { 19     edge[NE].v=v; 20     edge[NE].cap=cap; 21     edge[NE].next=head[u]; 22     head[u]=NE++; 23  24     edge[NE].v=u; 25     edge[NE].cap=0; 26     edge[NE].next=head[v]; 27     head[v]=NE++; 28 } 29  30 int level[MAXN],gap[MAXN]; 31 void bfs(int vt) 32 { 33     memset(level,-1,sizeof(level)); 34     memset(gap,0,sizeof(gap)); 35     level[vt]=0; 36     gap[0]++; 37     queue
           
            que; 38 que.push(vt); 39 while(!que.empty()){ 40 int u=que.front(); 41 que.pop(); 42 for(int i=head[u];i!=-1;i=edge[i].next){ 43 int v=edge[i].v; 44 if(level[v]!=-1)continue; 45 level[v]=level[u]+1; 46 gap[level[v]]++; 47 que.push(v); 48 } 49 } 50 } 51 52 int pre[MAXN],cur[MAXN]; 53 int SAP(int vs,int vt) 54 { 55 bfs(vt); 56 memset(pre,-1,sizeof(pre)); 57 memcpy(cur,head,sizeof(head)); 58 int u=pre[vs]=vs,aug=inf,maxflow=0; 59 gap[0]=NV; 60 while(level[vs]
            
             0&&level[u]==level[v]+1){ 65 flag=true; 66 aug=min(aug,edge[i].cap); 67 pre[v]=u; 68 u=v; 69 if(v==vt){ 70 maxflow+=aug; 71 MAX=max(MAX,aug); 72 for(u=pre[u];v!=vs;v=u,u=pre[u]){ 73 edge[cur[u]].cap-=aug; 74 edge[cur[u]^1].cap+=aug; 75 } 76 aug=inf; 77 } 78 break; 79 } 80 } 81 if(flag)continue; 82 int minlevel=NV; 83 for(int i=head[u];i!=-1;i=edge[i].next){ 84 int v=edge[i].v; 85 if(edge[i].cap>0&&level[v]