题目链接：

今天掉坑多次。

做了几道题，发现从源点出来的边和进入汇点的边都在题目中出来过。

POJ真是坑，交G++一直wa,检查代码检查了好几遍，无望看discuss，才知道交C++是RE，才知道数组越界了。

手写了Floyd，写成 i,j,k,wa了，突然想到以前遇到过这种问题。

看昂神解释明白了。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 using namespace std; 8 #define next Next 9 const int inf = 0x3f3f3f3f; 10 const int maxn=500; 11 int level[maxn]; 12 int iter[maxn]; 13 int head[maxn],tot; 14 struct edge{ 15 int to,cap,Next; 16 } e[80805]; ///此处应为边的两倍，加一条容量为0的反向边 17 void init(){ 18 memset(head,-1,sizeof(head)); 19 tot=0; 20 } 21 void add(int from,int to,int cap){ 22 e[tot].Next=head[from]; 23 e[tot].to=to; 24 e[tot].cap=cap; 25 head[from]=tot; 26 tot++; 27 } 28 void addedge(int from,int to,int cap){ 29 add(from,to,cap); 30 add(to,from,0); 31 } 32 void bfs(int s){ 33 memset(level,-1,sizeof(level)); 34 queue
           
             q; 35 level[s]=0; 36 q.push(s); 37 while(!q.empty()){ 38 int v=q.front(); q.pop(); 39 for(int i=head[v];~i;i=e[i].Next){ 40 edge &ed=e[i]; 41 if(ed.cap>0&&level[ed.to]<0){ 42 level[ed.to]=level[v]+1; 43 q.push(ed.to); 44 } 45 } 46 } 47 } 48 int dfs(int v,int t,int f){ 49 if(v==t) return f; 50 for(int &i=iter[v];~i;i=e[i].Next){ 51 edge &ed=e[i]; 52 if(ed.cap>0&&level[v]
            
             0){ 55 ed.cap-=d; 56 e[i^1].cap+=d; 57 return d; 58 } 59 } 60 } 61 return 0; 62 } 63 int max_flow(int s,int t){ 64 int flow=0; 65 while(1){ 66 bfs(s); 67 if(level[t]<0) return flow; 68 memcpy(iter,head,sizeof(iter)); 69 int f; 70 while((f=dfs(s,t,inf))>0){ 71 flow+=f; 72 } 73 } 74 } 75 int niu[maxn],capacity[maxn]; 76 typedef long long ll; 77 ll dp[maxn][maxn]; 78 void floyd(int n) 79 { 80 for(int k=1;k<=n;k++) 81 { 82 for(int i=1;i<=n;i++) 83 { 84 //if(i==j) continue; 85 for(int j=1;j<=n;j++) 86 { 87 if(i==k||j==k||i==j) continue; 88 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]); 89 } 90 } 91 } 92 } 93 int f,p; 94 void cons(ll T,int s,int t) 95 { 96 init(); 97 for(int i=1;i<=f;i++) 98 { 99 addedge(s,i,niu[i]);100 addedge(i,i+f,inf);101 addedge(i+f,t,capacity[i]);102 }103 for(int i=1;i<=f;i++)104 {105 for(int j=1;j<=f;j++)106 {107 if(i==j) continue;108 if(dp[i][j]<=T)109 {110 addedge(i,j+f,inf);111 }112 }113 }114 }115 int main()116 {117 int sum = 0;118 scanf("%d %d",&f,&p);119 for(int i=1;i<=f;i++)120 {121 scanf("%d %d",&niu[i],&capacity[i]);122 sum += niu[i];123 }124 for(int i=1;i<=f;i++)125 {126 for(int j=1;j<=f;j++)127 {128 dp[i][j] = 1e15;129 }130 }131 for(int i=1;i<=p;i++)132 {133 int x,y;134 ll w;135 scanf("%d %d %lld",&x,&y,&w);136 dp[x][y] = min(dp[x][y],w); ///一定要注意两点之间的有多条边的情况137 dp[y][x] = dp[x][y];138 }139 floyd(f);140 ll l = 0,r = 2000000000000LL;141 ll mid = 0;142 int s,t;143 s = 420,t = 421; ///s,t一定要在head数组范围内144 int flow = 0;145 ll ans = 0;146 while(l<=r)147 {148 mid = (l+r)/2LL;149 cons(mid,s,t);150 flow = max_flow(s,t);151 // printf("%lld %d\n",mid,flow);152 if(flow==sum)153 {154 ans = mid;155 r = mid-1;156 }157 else158 {159 l = mid+1;160 }161 }162 if(ans==0)163 {164 puts("-1");165 }166 else167 {168 printf("%lld\n",ans);169 }170 return 0;171 }172 /*173 3 4174 7 2175 0 4176 2 6177 1 2 40178 1 2 70179 1 2 90180 1 2 120181 */