Posted on 2010-09-30 19:58
成幸毅 阅读(395)
评论(0) 编辑 收藏 引用
题目中的要求是求路上最长的一部分中的边最短。每条边只能经过一次,FJ要去T次。每次都是找最短路径,先得排序,可以用参数搜索,所谓参数搜索就去用一个量去尝试,最大流做为判定,然后寻找最优值。
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x7fffffff;
const int EMAXN = 40001;
const int VMAXN = 201;
int c[VMAXN][VMAXN];
int d[VMAXN];
int s,t;
int vex;
int num[VMAXN],pre[VMAXN];
int n,m,g,u,v,w;
struct node {
int u,v,w;
}edge[EMAXN];
bool cmp(node a,node b) {
return a.w < b.w;
}
void ini_d(int n,int s,int t)
{
int k;
queue<int>Q;
memset(d,1,sizeof(d));
memset(num,0,sizeof(num));
Q.push(t);
d[t]=0;
num[0]=1;
while (!Q.empty())
{
k=Q.front(),Q.pop();
for (int i=0;i<vex+1;i++)
{
if (d[i]>=vex+1&&c[i][k]>0)
{ d[i]=d[k]+1;
Q.push(i);
num[d[i]]++;
}
}
}
}
int findAlowArc(int i)
{
int j;
for (j=0;j<vex+1;j++) if (c[i][j]>0&&d[i]==d[j]+1) return j;
return -1;
}
int reLable(int i)
{
int mm=INT_MAX;
for (int j=0;j<vex+1;j++)
if (c[i][j]>0) mm=min(mm,d[j]+1);
return mm==INT_MAX?m:mm;
}
int maxFlow(int vex,int s,int t)
{
ini_d(vex,s,t);
int flow=0,i=s,j;
int delta;
memset(pre,-1,sizeof(pre));
while (d[s]<vex+1)
{
j=findAlowArc(i);
if (j>=0)
{
pre[j]=i;
i=j;
if (i==t)
{
delta=INT_MAX;
for (i=t;i!=s;i=pre[i]) delta=min(delta,c[pre[i]][i]);
for (i=t;i!=s;i=pre[i]) c[pre[i]][i] -= delta, c[i][pre[i]] += delta;
flow += delta;
}
}
else
{
int x=reLable(i);
num[x]++;
num[d[i]]--;
if (num[d[i]]==0) return flow;
d[i]=x;
if (i!=s) i=pre[i];
}
}
return flow;
}
bool solve(int x) {
memset(c,0,sizeof(c));
for(int i = 0; i <= x;i++) {
c[edge[i].u][edge[i].v]++;
c[edge[i].v][edge[i].u]++;
}
int temp = maxFlow(vex,s,t);
if(temp >= g) return true;
else return false;
}
int main() {
while(scanf("%d%d%d",&n,&m,&g) != EOF) {
for(int i = 0; i < m; i++) {
scanf("%d%d%d",&u,&v,&w);
edge[i].u = u;
edge[i].v = v;
edge[i].w = w;
}
sort(edge,edge+m,cmp);
s = 1,t = n;
vex = n;
int l = 0, r = m,mid;
while(l < r) {
mid = (l + r)/2;
if(solve(mid))
r = mid;
else
l = mid + 1;
}
printf("%d\n",edge[r].w);
}
return 0;
}