POJ2253
本题的意思是求出点1到点2之间所有路间，每条路的最大边的最小值。所以根据这个只需要对每两个点进行松弛操作，然后在松弛操作中进行最大边选取即可。
至于为什么在这里选择了floyd算法，那是因为这两个点之间存在极其多的路径可供选择，而这里需要讨论每一条路的最大边，然后综合求最小值，所以这个很明显不能用普通的最短路算法来实现。这就需要floyd里这种类似动态规划的思想来解决是比较好的。在这里，所谓的松弛操作就是：已知a，b两点间存在一条通路，权值为w，假如在中间插入点c，并且a，c两点间存在一条权值为w1的通路，c，b两点间存在一条权值为w2的通路，且w>w1,w>w2，则w=max（w1,w2），这就是所谓最大边的最小值选取，即认为w是a与b间的最大边，w1与w2之间的最大边是a->c->b这条路的最大边。
初始化的时候认为“最大边”是两点间距。
import java.io.*; import java.text.*; import java.math.*; import java.util.*; public class Main { public static class Point { int x,y; public Point(int a,int b) { this.x=a; this.y=b; } } public static double distance(int x1,int x2,int y1,int y2) { return Math.sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); } public static void floyd(int limit1) { for(int k=1;k<=limit1;k++) { for(int i=1;i<=limit1;i++) { for(int j=1;j<=limit1;j++) { if(dis[i][j]>dis[i][k]&&dis[i][j]>dis[k][j]) dis[i][j]=Math.max(dis[i][k],dis[k][j]); } } } } static double dis[][]=new double[450][450]; static Point points[]=new Point[1322]; public static void main(String args[])throws IOException { BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); int cases=0; while(st.nextToken()!=StreamTokenizer.TT_EOF) { int n=(int)st.nval; if(n==0) break; for(int i=1;i<=n;i++) { int tmp1,tmp2; st.nextToken();tmp1=(int)st.nval; st.nextToken();tmp2=(int)st.nval; points[i]=new Point(tmp1,tmp2); } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dis[i][j]=dis[j][i]=distance(points[i].x,points[j].x,points[i].y,points[j].y); floyd(n); DecimalFormat df=new DecimalFormat("0.000"); pw.println("Scenario #"+(++cases)); pw.println("Frog Distance = "+df.format(dis[1][2])); pw.println(""); } pw.flush(); } }POJ1797
本题的要求是求1到n所有路径中最小值的最大值。由于数据较大，不能用floyd进行松弛，所以这里选择了spfa。
这里的松弛操作是对于a->b这样一条路，从1到b点的所有路径中最小值的最大值为从从min(1到a点的所有路径中最小值的最大值,w(a,b))，一直更新这个答案即可。
#include<pch.h> #include <iostream> #include <cstdio> #include <bits/stdc++.h> #include <queue> #include <map> #include <algorithm> #include <stack> #include <iomanip> #include <cstring> #include <cmath> #define endl '\n' #define DETERMINATION main #define For(a,b,c,d) for(int a=b;a<=c;a+=d) #pragma GCC optimize(2) #pragma warning(disable:4996) #define lldin(a) scanf("%lld", &a) #define println(a) printf("%lld\n", a) #define print(a) printf("%lld ", a) #define reset(a, b) memset(a, b, sizeof(a)) #define debug std::cout<<"procedures above are available"<<"\n"; #define BigInteger __int128 using namespace std; const long long INF = 2147483647; const double PI = acos(-1); typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int mod = 1e9 + 7; //template<typename T> //inline BigInteger nextBigInteger() //{ // BigInteger tmp = 0, si = 1;char c; c = getchar(); // while (!isdigit(c)) //{if (c == '-')si = -1;c = getchar();} // while (isdigit(c)) // {tmp = tmp * 10 + c - '0';c = getchar();} // return si * tmp; //} //std::ostream& operator<<(std::ostream& os, __int128 T) //{ // if (T<0) os<<"-";if (T>=10 ) os<<T/10;if (T<=-10) os<<(-(T/10)); // return os<<( (int) (T) >0 ? (int) (T) : -(int) (T) ) ; //} //void output(BigInteger x) //{ // if (x < 0) // {x = -x;putchar('-');} // if (x > 9) output(x / 10); // putchar(x % 10 + '0'); // } /**Operation Overlord 1944.6.6 Daybreak**/ /**Last Remote**/ ll cnt = 0, dis[123122]; ll relation[1500][1500]; ll Min(ll a, ll b) { if (b >= a) return a; else return b; } bool vis[322122]; void spfa(ll st, ll limit) { for (int i = 1; i <= limit; i++) { dis[i] = 0; vis[i] = false; } queue<ll>q; q.push(st); dis[st] = INF; vis[st] = true; while (!q.empty()) { ll current = q.front(); q.pop(); vis[current] = false; for (int i = 1; i <= limit; i++) { if (relation[current][i]) { if (dis[i] < min(dis[current], relation[current][i])) { dis[i] = min(dis[current], relation[current][i]); if (!vis[i]) { vis[i] = true; q.push(i); } } } } } } int DETERMINATION() { //std::ios::sync_with_stdio(false); //std::cin.tie(0), std::cout.tie(0); ll t; lldin(t); for (int y = 1; y <= t; y++) { ll n, m; lldin(n), lldin(m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) relation[i][j] = 0; for (int i = 1; i <= m; i++) { ll tmp1, tmp2, tmp3; lldin(tmp1), lldin(tmp2), lldin(tmp3); relation[tmp1][tmp2] = tmp3; relation[tmp2][tmp1] = tmp3; } spfa(1, n); printf("Scenario #%d:\n", y); println(dis[n]); puts(""); } return 0; }POJ3268
正向建边，可以把从x到每个点的返回距离求出来，并且开一个专门的数组把他们储存好。
反向建边，可以把从每个点到x的前往距离求出来（都是以x为起点），与上组内的数据对应相加，然后求最大值即可。
//#include<pch.h> #include <iostream> #include <cstdio> //#include <bits/stdc++.h> #include<queue> #include <map> #include <algorithm> #include <stack> #include <iomanip> #include <cstring> #include <cmath> #define DETERMINATION main #define lldin(a) scanf("%lld", &a) #define println(a) printf("%lld\n", a) #define print(a) printf("%lld ", a) #define reset(a, b) memset(a, b, sizeof(a)) #define debug cout<<"procedures above are available"<<endl; using namespace std; const int INF = 2147183646; //const double PI = acos(-1); typedef long long ll; //typedef unsigned long long ull; //typedef long double ld; //const int mod = 10000000; //const int tool_const = 19991126; //const int tool_const2 = 33; inline ll nextLong() { ll tmp = 0, si = 1; char c; c = getchar(); while (c > '9' || c < '0') { if (c == '-') si = -1; c = getchar(); } while (c >= '0' && c <= '9') { tmp = tmp * 10 + c - '0'; c = getchar(); } return si * tmp; } /**Maintain your determination.Nobody knows the magnificent landscape at his destination before the arrival with stumble.**/ /**Last Remote**/ struct node { ll next,to,value; }nodes[1231222]; ll heads[1312]; ll cnt=0; void cons(ll from,ll to,ll value) { nodes[++cnt]=node{heads[from],to,value}; heads[from]=cnt; } struct status { ll pos,dis; }; bool operator<(status a,status b) { return a.dis>b.dis; } ll dis[5400]; void spfa(ll st,ll limit) { for(int i=1;i<=limit;i++) dis[i]=INF; priority_queue<status>pq; pq.push(status{st,0}); dis[st]=0; while(!pq.empty()) { status current=pq.top(); pq.pop(); if(current.dis>dis[current.pos]) continue; else { for(int i=heads[current.pos];i!=-1;i=nodes[i].next) { ll t=nodes[i].to; if(dis[t]>dis[current.pos]+nodes[i].value) { dis[t]=dis[current.pos]+nodes[i].value; pq.push(status{t,dis[t]}); } } } } } struct tmpnode { ll from,to,value; }tmpnodes[2321112]; ll tmpans[12322]; int DETERMINATION() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); ll n,m,x; reset(heads,-1); cin>>n>>m>>x; for(int i=1;i<=m;i++) { ll tmp1,tmp2,tmp3; cin>>tmp1>>tmp2>>tmp3; tmpnodes[i].from=tmp1; tmpnodes[i+m].from=tmp2; tmpnodes[i].to=tmp2; tmpnodes[i+m].to=tmp1; tmpnodes[i].value=tmp3; tmpnodes[i+m].value=tmp3; } for(int i=1;i<=m;i++) cons(tmpnodes[i].from,tmpnodes[i].to,tmpnodes[i].value); spfa(x,n); for(int i=1;i<=n;i++) tmpans[i]+=dis[i]; reset(heads,-1); for(int i=m+1;i<=2*m;i++) cons(tmpnodes[i].from,tmpnodes[i].to,tmpnodes[i].value); spfa(x,n); ll ans=0; for(int i=1;i<=n;i++) { tmpans[i]+=dis[i]; ans=max(tmpans[i],ans); } cout<<ans<<endl; return 0; }POJ3259
求出一个负环就可以判断YES了
//#include<pch.h> #include <iostream> #include <cstdio> //#include <bits/stdc++.h> #include<queue> #include <map> #include <algorithm> #include <stack> #include <iomanip> #include <cstring> #include <cmath> #define DETERMINATION main #define lldin(a) scanf("%lld", &a) #define println(a) printf("%lld\n", a) #define print(a) printf("%lld ", a) #define reset(a, b) memset(a, b, sizeof(a)) #define debug cout<<"procedures above are available"<<endl; using namespace std; const int INF = 2147183646; const double PI = acos(-1); typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int mod = 10000000; const int tool_const = 19991126; const int tool_const2 = 33; inline ll nextLong() { ll tmp = 0, si = 1; char c; c = getchar(); while (c > '9' || c < '0') { if (c == '-') si = -1; c = getchar(); } while (c >= '0' && c <= '9') { tmp = tmp * 10 + c - '0'; c = getchar(); } return si * tmp; } /**Maintain your determination.Nobody knows the magnificent landscape at his destination before the arrival with stumble.**/ /**Last Remote**/ struct node { ll next,to,value; }nodes[324323]; ll heads[234323],cnt=0; void cons(ll from,ll to,ll value) { nodes[++cnt]=node{heads[from],to,value}; heads[from]=cnt; } ll dis[341222],cnt2[342322]; bool vis[3421122]; bool spfa(ll st,ll limit) { for(int i=1;i<=limit;i++) { dis[i]=INF; vis[i]=false; cnt2[i]=0; } queue<ll>q; q.push(st); dis[st]=0; vis[st]=true; while(q.empty()==false) { ll current=q.front(); q.pop(); vis[current]=false; for(int i=heads[current];i!=-1;i=nodes[i].next) { ll t=nodes[i].to; if(dis[t]>dis[current]+nodes[i].value) { dis[t]=dis[current]+nodes[i].value; if(cnt2[t]>limit) { //cout<<t<<endl; vis[t]=true; return true; } if(!vis[t]) { cnt2[t]++; q.push(t); vis[t]=true; } } } } return false; } int DETERMINATION() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); ll t; cin>>t; for(int y=1;y<=t;y++) { ll n,m,w; reset(heads,-1); cnt=0; cin>>n>>m>>w; for(int i=1;i<=m;i++) { ll tmp1,tmp2,tmp3; cin>>tmp1>>tmp2>>tmp3; cons(tmp1,tmp2,tmp3); cons(tmp2,tmp1,tmp3); //debug; } for(int i=1;i<=w;i++) { ll tmp1,tmp2,tmp3; cin>>tmp1>>tmp2>>tmp3; cons(tmp1,tmp2,-tmp3); } if(spfa(1,n)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }POJ1860
本题是一个关于货币兑换的问题，这类问题一般利用最长路松弛式判断图内是否存在正环（即走过这一个环之后收益会变大）。
在本题中这个式子是这个样子:dis[t]<(dis[current]-nodes[i].cost)*nodes[i].value
struct node { ll next,to; double value,cost; }nodes[523333]; ll heads[523333],cnt1=0; double dis[523332]; void construction(ll from,ll to,double value,double cost) { nodes[++cnt1]=node{heads[from],to,value,cost}; heads[from]=cnt1; } bool vis[352322]; ll cnt[341222]; bool spfa(ll st,ll limit,double v) { for(int i=1;i<=limit+87;i++) { dis[i]=(double)0; cnt[i]=0; vis[i]=false; } queue<ll>q; q.push(st); dis[st]=v; while(!q.empty()) { ll current=q.front(); q.pop(); vis[current]=false; for(int i=heads[current];i!=-1;i=nodes[i].next) { ll t=nodes[i].to; if(dis[t]<(dis[current]-nodes[i].cost)*nodes[i].value) { dis[t]=(dis[current]-nodes[i].cost)*nodes[i].value; //cout<<dis[t]<<endl; if(cnt[t]>=limit) return true; if(!vis[t]) { vis[t]=true; cnt[t]++; q.push(t); } } } } return false; } int DETERMINATION() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); ll n,m,s; ld v; cin>>n>>m>>s>>v; reset(heads,-1); for(int i=1;i<=m;i++) { ll a,b; double tmp1,tmp2,tmp3,tmp4; cin>>a>>b>>tmp1>>tmp2>>tmp3>>tmp4; construction(a,b,tmp1,tmp2); construction(b,a,tmp3,tmp4); } if(spfa(s,n,v)) cout<<"YES"<<endl; else cout<<"NO"<<endl; //cout<<dis[s]<<endl; return 0; }POJ3159
这是差分约束系统的一个题。
最短路表达式总是要满足dis[y]<=dis[x]+c，也即是dis[y]-dis[x]<=c，将题意中的不等式变换成差分约束方程组即可
struct node { ll next,to,value; }nodes[250000]; ll heads[30055]; ll cnt=0; void cons(ll from,ll to,ll value) { nodes[++cnt]=node{heads[from],to,value}; heads[from]=cnt; } struct status { ll pos,dis; }; bool operator<(status a,status b) { return a.dis>b.dis; } ll dis[57666]; void dijkstra(ll st,ll limit) { for(int i=1;i<=limit;i++) dis[i]=INF; dis[st]=0; priority_queue<status>pq; pq.push(status{st,0}); while(!pq.empty()) { status current=pq.top(); pq.pop(); if(current.dis>dis[current.pos]) continue; else { for(int i=heads[current.pos];i!=-1;i=nodes[i].next) { ll t=nodes[i].to; if(dis[t]>dis[current.pos]+nodes[i].value) { dis[t]=dis[current.pos]+nodes[i].value; pq.push(status{t,dis[t]}); } } } } } int DETERMINATION() { //ios::sync_with_stdio(false); //cin.tie(0),cout.tie(0); ll n,m; lldin(n),lldin(m); reset(heads,-1); for(int i=1;i<=m;i++) { ll tmp1,tmp2,tmp3; lldin(tmp1),lldin(tmp2),lldin(tmp3); cons(tmp1,tmp2,tmp3); } dijkstra(1,n); ll ans=0; println(dis[n]); return 0; }
