题意：给出一些牛棚，开始牛棚边有一些牛，牛棚之间有路相连，走一条路会花费固定的时间。牛在牛棚边吃草，下雨时牛得躲进牛棚，每个牛棚容量有限。
求在所有牛都能进牛棚时最少需要多少时间。
这题和POJ2112相似,不过这题要拆点,把每个点拆成两个点,如果直接连原图中的点，是不对的。网上找了大神的图
当二分到T = 70的时候，显然我们只加入了(2, 3)和(3, 4)两条无向边，因为只有这两对点间的最短距离小于等于70。但是从图中也可以看出，由于没有拆点，点2也可以通过这两条边到达点4，而实际上这是不允许的。也就是说我们所加的限制条件没有起到作用。由此可见，只有拆点才是正确的做法。
然后这题还要注意64位。。
详情见代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 using namespace std; 7 #define N 450 8 #define M 88888 9 typedef long long lld; 10 typedef unsigned long long u64; 11 const int inf= 0x7fffffff; 12 const lld dis_inf= 10000000000000000LL; 13 struct Edge 14 { 15 int v,w,next; 16 Edge(){} 17 Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){} 18 }edge[M]; 19 int pre[N],cur[N],dis[N],gap[N]; 20 int size,head[N]; 21 int F,P,nv,num,s,e; 22 lld map[N][N]; 23 int cow[N],col[N]; 24 lld mid; 25 void InsertEdge(int u,int v,int w) // 建边 26 { 27 edge[size] = Edge(v,w,head[u]); 28 head[u] = size++; 29 edge[size] = Edge(u,0,head[v]); 30 head[v] = size++; 31 } 32 void Floyd() //Floyd求两点间的最短距离 33 { 34 for(int k=1; k<=F; k++) 35 { 36 for(int i=1; i<=F; i++) 37 { 38 if(k==i||map[i][k]==dis_inf) continue; 39 for(int j=1; j<=F; j++) 40 { 41 if(k==j||map[k][j]==dis_inf) continue; 42 if(map[i][j] > map[i][k]+map[k][j]) 43 map[i][j] = map[i][k] + map[k][j]; 44 } 45 } 46 } 47 } 48 void Init() //建图 49 { 50 size = 0; 51 memset(head,-1,sizeof(head)); 52 for(int i=1; i<=F; i++) 53 { 54 for(int j=1; j<=F; j++) 55 { 56 if(map[i][j] <= mid) 57 InsertEdge(i,F+j,inf); //如果两点间的距离<=mid,两点间建条权值为inf的边，表示这条边可以容纳无数奶牛 58 } 59 InsertEdge(s,i,col[i]); //对源点到每个草地建边，权值为草地的容量 60 InsertEdge(i+F,e,cow[i]); //对每个草地的拆点到汇点建边，权值为草地现有的牛 61 } 62 } 63 int Isap(int st,int ed,int n) { //Isap模板 64 for(int i=0; i<=n; i++) { 65 cur[i] = head[i]; 66 gap[i] = dis[i] = 0; 67 } 68 int u = pre[st] = st; 69 int aug = inf ,maxflow = 0; 70 while(dis[st] < n) { 71 loop: 72 for(int &i=cur[u]; i!=-1; i=edge[i].next) { 73 int v = edge[i].v; 74 if(edge[i].w && dis[u] == dis[v] + 1) { 75 aug = min(aug,edge[i].w); 76 pre[v] = u; 77 u = v; 78 if(v==ed) { 79 maxflow += aug; 80 for(u=pre[u]; v!=st; v=u,u=pre[u]) { 81 edge[cur[u]].w -= aug; 82 edge[cur[ u]^1].w += aug; 83 } 84 aug = inf; 85 } 86 goto loop; 87 } 88 } 89 int mindis = n; 90 for(int i=head[u]; i!=-1; i=edge[i].next) { 91 int v = edge[i].v; 92 if(edge[i].w && dis[v]<mindis) { 93 cur[u] = i; 94 mindis = dis[v]; 95 } 96 } 97 if(--gap[dis[u]]==0) break; 98 gap[dis[u] = mindis+1]++; 99 u = pre[u]; 100 } 101 return maxflow; 102 } 103 104 int main() 105 { 106 while(scanf("%d%d",&F,&P)!=EOF) 107 { 108 s = 0 ; e = 2*F+1 ; nv = e+1; 109 //源点，汇点，节点数 110 num = 0; //奶牛总数 111 for(int i=1; i<=F; i++) 112 { 113 scanf("%d%d",&cow[i],&col[i]); 114 num += cow[i]; 115 } 116 for(int i=1; i<=F; i++) 117 for(int j=1; j<=F; j++) 118 map[i][j]= i==j ? 0 : dis_inf; 119 lld l = 0 ,r = 0; //二分的左右界 120 int u,v,w; 121 for(int i=1; i<=P; i++) 122 { 123 scanf("%d%d%d",&u,&v,&w); 124 r += w; 125 if(w < map[u][v]) map[u][v] = map[v][u] = w; 126 } 127 Floyd(); 128 int flag = 1; //标志是否找到合适的距离 129 while(l <= r) 130 { 131 mid = l + (r-l)/2; 132 Init(); 133 if(Isap(s,e,nv)==num) 134 { 135 r = mid-1; 136 flag = 0; 137 } 138 else l = mid + 1; 139 } 140 if(flag) printf("-1 "); 141 else printf("%lld ",l); 142 } 143 return 0; 144 }