//題意是求起點(diǎn)到終點(diǎn),滿(mǎn)足走K次不重復(fù)的路(任何一段都不能相同),最大邊中的值最小
/**
*6 5 1
*1 2 1
*2 3 4
*3 6 5
*1 4 1
*4 5 1
*5 6 6
從1到6有 2條路徑 1-2-3-6 最大邊值為 5
1-4-5-6 最大邊值為 6
因?yàn)橹蛔咭粭l 所以最大邊值的最小為5
若走2條 則最大邊值的最小為6
具體做法:
先分別構(gòu)建源點(diǎn)與匯點(diǎn) 源點(diǎn)為s = 0, 匯點(diǎn)為t = n + 1, 因?yàn)橐獫M(mǎn)足走K次所以 分別連接s-1,n-t流量都為K.二分枚舉最大邊的值.
先left = 0, right = 1000000;(right 可以是大于等于[and with a positive length that does not exceed 1,000,000.]要求的值)
mid = (left + right) >> 1; 如果某條邊(u,v)的值滿(mǎn)足<=mid,則連接u,v, 流為1.最大流的結(jié)果若是<K說(shuō)明mid不是所求的值,要增大這個(gè)值
left = mid + 1;如果最大流為K說(shuō)明mid可以滿(mǎn)足但是還要確定是否有比他小的數(shù)使得流也為K,所以right = mid - 1.二分搜完最后結(jié)果就是left
若說(shuō)錯(cuò)了 求指教~~
**/
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXV = 410;
const int MAXE = 200010;
const int inf = 1 << 29;
int head[MAXV], N;
struct Edge {
int v, next, w;
}edge[MAXE], tmp[MAXE];
int n, m, s, t, cnt, ans;
void add(int u, int v, int w) {
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[ u ];
head[ u ] = cnt++;
edge[cnt].v = u;
edge[cnt].w = w;
edge[cnt].next = head[ v ];
head[ v ] = cnt++;
}
int sap() {
int pre[MAXV], cur[MAXV], dis[MAXV], gap[MAXV];
int flow = 0, aug = inf, u;
bool flag;
for(int i = 0; i <= N; ++ i) {
cur[ i ] = head[ i ];
gap[ i ] = dis[ i ] = 0;
}
gap[ s ] = N;
u = pre[ s ] = s;
while(dis[ s ] < N) {
flag = 0;
for(int &j = cur[ u ]; j != -1; j = edge[ j ].next) {
int v = edge[ j ].v;
if(edge[ j ].w > 0 && dis[ u ] == dis[ v ] + 1) {
flag = 1;
if(edge[ j ].w < aug) aug = edge[ j ].w;
pre[ v ] = u;
u = v;
if(u == t) {
flow += aug;
while(u != s) {
u = pre[ u ];
edge[cur[ u ] ].w -= aug;
edge[cur[ u ]^1].w += aug;
}
aug = inf;
}
break;
}
}
if(flag) continue;
int mindis = N;
for(int k = head[ u ]; k != -1; k = edge[ k ].next) {
int v = edge[ k ].v;
if(edge[ k ].w > 0 && dis[ v ] < mindis) {
mindis = dis[ v ];
cur[ u ] = k;
}
}
if( (--gap[dis[ u ]]) == 0) break;
dis[ u ] = mindis + 1;
gap[dis[ u ]] ++;
u = pre[ u ];
}
return flow;
}
int main() {
int i, j;
int mm;
while(~scanf("%d %d %d", &m, &n, &mm)) {
for(i = 0; i < n; ++ i) {
scanf("%d %d %d", &tmp[ i ].v, &tmp[ i ].next, &tmp[ i ].w);
}
int left = 0, right = 1000000, mid;
while(left <= right) {
mid = (left + right) >> 1;
cnt = 0; s = 0; t = m - 1; N = t + 1;
memset(head,-1,sizeof(head));
for(i = 0; i < n; ++ i) {
if(tmp[ i ].w <= mid) {
add(tmp[ i ].v - 1, tmp[ i ].next - 1, 1);
}
}
ans = sap();
if(ans >= mm) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
printf("%d\n", left);
}
return 0;
}