題目很長(zhǎng)，說白了就是選擇一個(gè)子圖使得圖中最長(zhǎng)邊最短并且從a到b的弱獨(dú)立軌數(shù)目>t
很經(jīng)典的網(wǎng)絡(luò)流做法，就不多說了- -順便放出網(wǎng)絡(luò)流模板- -這個(gè)模板曾經(jīng)過掉過2W個(gè)點(diǎn)，10W個(gè)邊的圖。。。
1 # include <cstdio>
2 # include <cstring>
3 # include <algorithm>
4 using namespace std;
5 # define typec int // type of cost
6 # define inf 0xffffff // max of cost
7 # define E 200000
8 # define N 300
9 struct edge { int x, y, nxt; typec c; } bf[E];
10 int ne, head[N], cur[N], ps[N], dep[N];
11 void init()
12 {
13 ne=0;
14 memset(head,-1,sizeof(head));
15 }
16 void addedge(int x, int y, typec c)
17 { // add an arc(x -> y, c); vertex: 0 ~ n-1;
18 bf[ne].x = x; bf[ne].y = y; bf[ne].c = c;
19 bf[ne].nxt = head[x]; head[x] = ne++;
20 bf[ne].x = y; bf[ne].y = x; bf[ne].c = 0;
21 bf[ne].nxt = head[y]; head[y] = ne++;
22 }
23 typec flow(int n, int s, int t)
24 {
25 typec tr, res = 0;
26 int i, j, k, f, r, top;
27 while (1)
28 {
29 memset(dep, -1, n * sizeof(int));
30 for (f = dep[ps[0] = s] = 0, r = 1; f != r; )
31 for (i = ps[f++], j = head[i]; j!=-1; j = bf[j].nxt)
32 {
33 if (bf[j].c && -1 == dep[k = bf[j].y])
34 {
35 dep[k] = dep[i] + 1; ps[r++] = k;
36 if (k == t)
37 { f = r; break; }
38 }
39 }
40 if (-1 == dep[t]) break;
41 memcpy(cur, head, n * sizeof(int));
42 for (i = s, top = 0; ; )
43 {
44 if (i == t)
45 {
46 for (k = 0, tr = inf; k < top; ++k)
47 if (bf[ps[k]].c < tr)
48 tr = bf[ps[f = k]].c;
49 for (k = 0; k < top; ++k)
50 bf[ps[k]].c -= tr, bf[ps[k]^1].c += tr;
51 res += tr; i = bf[ps[top = f]].x;
52 }
53 for (j=cur[i]; cur[i] != -1; j = cur[i] = bf[cur[i]].nxt)
54 if (bf[j].c && dep[i]+1 == dep[bf[j].y]) break;
55 if (cur[i] != -1)
56 {
57 ps[top++] = cur[i];
58 i = bf[cur[i]].y;
59 }
60 else
61 {
62 if (0 == top) break;
63 dep[i] = -1; i = bf[ps[--top]].x;
64 }
65 }
66 }
67 return res;
68 }
69 //start
70 int len[50000],data[50000][3];
71 int main()
72 {
73 // freopen("input.txt","r",stdin);
74 // freopen("output.txt","w",stdout);
75 int n,p,t;
76 scanf("%d%d%d",&n,&p,&t);
77 for(int i=0;i<p;i++)
78 {
79 scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);
80 len[i]=data[i][2];
81 }
82 sort(len,len+p);
83 int e=unique(len,len+p)-len-1,s=0;
84 while(s<=e)
85 {
86 int mid=(s+e)/2;
87 init();
88 for(int i=0;i<p;i++)
89 if(data[i][2]<=len[mid])
90 {
91 addedge(data[i][0],data[i][1],1);
92 addedge(data[i][1],data[i][0],1);
93 }
94 int res=flow(n+1,1,n);
95 if(res>=t)
96 e=mid-1;
97 else
98 s=mid+1;
99 }
100 printf("%d\n",len[s]);
101 // system("pause");
102 return 0;
103 }
104