gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 3662--Telephone Lines(二分枚举 + Dij)
  1#include <cstdio>
  2#include <cstring>
  3#include <algorithm>
  4using namespace std;
  5
  6const int INTMAX = 1000;
  7const int SIZE = 20001;
  8const int MAXN = 1001;
  9
 10struct EDGE
 11{
 12    int x, y, len;
 13
 14}edge[SIZE];
 15
 16bool cmp1 ( const EDGE& a, const EDGE& b )
 17{
 18    if ( a.x != b.x )
 19        return ( a.x < b.x );
 20    else
 21        return ( a.y <= b.y );
 22}
 23bool cmp2 ( const EDGE& a, const EDGE& b )
 24{
 25    return ( a.len <= b.len );
 26}
 27
 28int N, P, K;
 29int arr[SIZE], mark[MAXN], temp[MAXN], biArr[SIZE];
 30
 31bool Dij(const int& length)
 32{
 33    int i, j, k, t, min;
 34
 35    for ( i = 0; i < P; ++i )
 36    {
 37        if ( edge[i].len > length )
 38            arr[i] = 1;
 39        else
 40            arr[i] = 0;
 41    }
 42
 43    temp[1] = -1;
 44    for ( i = 2; i <= N; ++i )
 45    {
 46        temp[i] = INTMAX; 
 47    }
 48
 49    for ( i = mark[1]; edge[i].x == 1; ++i )
 50    {
 51        temp[edge[i].y] = arr[i];
 52    }
 53
 54    for ( i = 2; i <= N; ++i )
 55    {
 56        min = INTMAX;
 57        k = 1;
 58        for ( j = 2; j <= N; ++j )
 59        {
 60            if ( temp[j] != -1 && temp[j] < min )
 61            {
 62                min = temp[j];
 63                k = j;
 64            }
 65        }
 66        for ( j = mark[k]; edge[j].x == k; ++j )
 67            if ( temp[edge[j].y] > temp[k] + arr[j] && temp[k] != -1 )
 68                temp[edge[j].y] = temp[k] + arr[j];
 69        
 70        if ( k == N )
 71            t = temp[k];
 72        temp[k] = -1;
 73    }
 74
 75    if ( t <= K )
 76        return true;
 77    return false;
 78}
 79
 80void Solve()
 81{
 82    int i, j, mid, left, right;
 83
 84    sort( edge, edge + P, cmp2 );
 85
 86    j = 0;
 87    biArr[j++] = 0;
 88    biArr[j++] = edge[0].len;
 89    for ( i = 1; i < P; ++i )
 90    {
 91        if ( edge[i].len != edge[i - 1].len )
 92            biArr[j++] = edge[i].len;
 93    }
 94
 95    memset(mark, 0, sizeof(mark));
 96    sort(edge, edge + P, cmp1);
 97
 98    mark[edge[0].x] = 0;
 99    for ( i = 1; i < P; ++i )
100    {
101        if ( edge[i].x != edge[i - 1].x )
102            mark[edge[i].x] = i;
103    }
104
105
106    left = 0, right = j - 1;
107    while ( left <= right )
108    {
109        mid = (left + right) >> 1;
110        if ( Dij( biArr[mid] ) )
111            right = mid - 1;
112        else
113            left = mid + 1;
114            
115    }
116
117    if ( Dij( biArr[left] ) )
118        printf("%d\n", biArr[left]);
119    else
120        printf("-1\n");
121}
122
123int main()
124{
125//    freopen("1.txt", "r", stdin);
126
127    int i, j, x, y, l;
128
129    scanf("%d %d %d", &N, &P, &K);
130
131    for ( i = 0, j = 0; i < P; ++i )
132    {
133        scanf("%d %d %d", &x, &y, &l);
134        edge[j].x = x; edge[j].y = y; edge[j++].len = l;
135        edge[j].x = y; edge[j].y = x; edge[j++].len = l;
136    }
137
138    P <<= 1;
139
140    Solve();
141
142    return 0;
143}
posted on 2009-03-19 21:00 巫 阅读(401) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理