![](\"http:\/\/61.187.179.132:8080\/JudgeOnline\/images\/1486_1.jpg\")
<\/p>\n
![](\"http:\/\/61.187.179.132:8080\/JudgeOnline\/images\/1486_2.jpg\")
<\/p>\n
Input <\/strong><\/p>\n<\/p>\n Output <\/strong><\/p>\n<\/p>\n Sample Input <\/strong><\/p>\n Sample Output <\/strong><\/p>\n Source #include <vector> [HNOI2009]\u6700\u5c0f\u5708 Time Limit:10000MS Memory Limit:65536KTotal Submit:93 Accepted:37 Case Time Limit:1000MS Description Input Output Sample Input Sample Output Source\u8fd9\u9053\u9898\u662f\u6700\u6700\u57fa\u672c\u7684\u4e8c\u5206\u5224\u5b9a+\u67e5\u627e\u8d1f\u73af\u7684\u95ee\u9898\u4e86\u3002\u3002\u76f4\u63a5\u4e0aDfs\u67e5\u627e\u8d1f\u73af\u5c31OK\u4e86(*^__^*) \u3002\u3002\u3002Code\uff1a #include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define tr(i,x) for(eit i=x.begin();i!=x.end();i++)const int inf=~0U>>1,maxn=3000;using namespace std;int n,m;struct Edge{ int t; double c,oc; Edge(int _t,double _c):t(_t),oc(_c){}};typedef vector<Edge>::iterator eit;vector<Edge> E[maxn];double D;bool vis[maxn]={0},Find;double Dist[maxn];void dfs(int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/226"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=226"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/226\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=226"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=226"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=226"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u8fd9\u9053\u9898\u662f\u6700\u6700\u57fa\u672c\u7684\u4e8c\u5206\u5224\u5b9a+\u67e5\u627e\u8d1f\u73af\u7684\u95ee\u9898\u4e86\u3002\u3002\u76f4\u63a5\u4e0aDfs\u67e5\u627e\u8d1f\u73af\u5c31OK\u4e86(*^__^*) \u3002\u3002\u3002
Code\uff1a
<\/strong><\/p>\n
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(eit i=x.begin();i!=x.end();i++)
const int inf=~0U>>1,maxn=3000;
using namespace std;
int n,m;
struct Edge
{
int t;
double c,oc;
Edge(int _t,double _c):t(_t),oc(_c){}
};
typedef vector<Edge>::iterator eit;
vector<Edge> E[maxn];
double D;
bool vis[maxn]={0},Find;
double Dist[maxn];
void dfs(int x)
{
vis[x]=true;double cost=Dist[x],ncost;
tr(e,E[x])if((ncost=cost+e->c)>Dist[e->t])
{
if(!vis[e->t]){Dist[e->t]=ncost;dfs(e->t);}
else Find=true;
if(Find)break;
}
vis[x]=false;
}
bool Check(double _D)
{
D=_D;
rep(i,n)tr(e,E[i])e->c=D-e->oc;
Find=false;
rep(i,n)Dist[i]=0;
rep(i,n){dfs(i);if(Find)return true;}
return false;
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>n>>m;
int s,t;double c;
rep(i,m)scanf("%d %d %lf",&s,&t,&c),–s,–t,E[s].pb(Edge(t,c));
double r=1e7,l=-r;
while(r-l>1e-9)
{
double m=(l+r)\/2;
if(Check(m))r=m;
else l=m;
}
printf("%0.8lfn",l);
}<\/p>\n","protected":false},"excerpt":{"rendered":"