uva11090

링크:클릭하여 링크 열기
제목: 방향도를 제시하고 그 중 어느 고리의 각 변의 권한과 변수 나누기가 가장 작은지 묻는다
코드:

#include <queue>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const double INF=0x3f3f3f3f;
int n,m;
double d[55];
struct node{
    int from,to;
    double cost;
}G[2500];
bool judge(double v){
    int i,j;
    memset(d,0,sizeof(d));
    for(i=0;i<m;i++)
    G[i].cost-=v;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            node e=G[j];
            if(d[e.to]>d[e.from]+e.cost){
            d[e.to]=d[e.from]+e.cost;
            if(i==n-1)
            return 1;
            }
        }
    }
    return 0;
}                                               //       
int main(){
    double l,r,mid;
    int t,k,i,j;
    scanf("%d",&t);
    for(k=1;k<=t;k++){
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        scanf("%d%d%lf",&G[i].from,&G[i].to,&G[i].cost);
        if(judge(INF)==0){                      //         
            printf("Case #%d: No cycle found.
",k);
            continue;
        }
        for(j=0;j<m;j++)
        G[j].cost+=INF;
        l=0,r=INF;
        for(i=0;i<100;i++){                     //    ，          
            mid=(l+r)/2;                        //        0
            if(judge(mid))
            r=mid;
            else
            l=mid;
            for(j=0;j<m;j++)
            G[j].cost+=mid;
        }
        printf("Case #%d: %.2lf
",k,l);
    }
    return 0;
}