題目鏈接：點擊查看
題目大意：給出一張三角形的無向圖，如下圖所示
求出從點 ( 1 , 1 ) 到點 ( n , n ) 找到一條最長路，且每條邊至多遍歷一次，輸出最長路的權(quán)值以及路徑
題目分析：點 ( 1 ,?1 ) 到點 ( n , n ) 的一條最長路，且每條邊至多遍歷一次，不難想到歐拉通路，但歐拉通路的定義是，只有起點和終點兩個奇度點，其余的點都是偶度點才行，對于初始時給出的圖，所有的點都是偶度點，所以考慮刪邊，在確保其余點度數(shù)奇偶性不變的前提下，如果想要通過刪邊將起點和終點變?yōu)槠娑赛c，那么只能刪除一條從起點到終點的路徑
現(xiàn)在設(shè)總權(quán)值為 sum，再設(shè)刪掉的路徑的權(quán)值為 res，那么最后求出歐拉通路的答案就是 sum - res 了，因為 sum 是不變的，想要讓答案盡可能的大，那么就只能讓 res 盡可能的小，這就轉(zhuǎn)換成最短路問題了
所以本題的解法就是，先求出點 ( 1 , 1 ) 到點 ( n , n ) 的最短路，在原圖中將其刪除，最后從點 ( 1 ,1 ) 跑一遍歐拉通路就好了
因為求最短路的過程中可能會爆 int ，所以我用了封裝的迪杰斯特拉，求歐拉通路以及輸出結(jié)果的函數(shù)都扔到里面去了
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=310;int id[N][N],n;pair<int,int>p[N*N];template<typename T>
struct Dij
{const static int N=310*310;const static int M=N*10;struct Edge{int to,next;bool vis;T w;}edge[M];int head[N],cnt;//鏈式前向星int pre[N][2]; T d[N];stack<int>ans;bool vis[N];void addedge(int u,int v,T w){edge[cnt].vis=false;edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;}struct Node{int to;T w;Node(int TO,T W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;}};void Dijkstra(int st){priority_queue<Node>q;d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;T w=edge[i].w;if(d[v]>d[u]+w)//更新 {pre[v][0]=u;pre[v][1]=i;d[v]=d[u]+w;q.push(Node(v,d[v]));}}}int pos=id[n][n];do{int id=pre[pos][1];edge[id].vis=edge[id^1].vis=true;pos=pre[pos][0];}while(pos!=st);}void dfs(int u){for(int i=head[u];i!=-1;i=edge[i].next){if(edge[i].vis)continue;edge[i].vis=edge[i^1].vis=true;dfs(edge[i].to);}ans.push(u);}void print(){printf("%d\n",ans.size());while(ans.size()){int id=ans.top();ans.pop();if(ans.empty())printf("%d %d\n",p[id].first,p[id].second);elseprintf("%d %d ",p[id].first,p[id].second);}}void init(){while(ans.size())ans.pop();for(int i=0;i<=n*n;i++){head[i]=-1;vis[i]=0;d[i]=0x3f3f3f3f3f3f3f3f;}cnt=0; }
};Dij<LL>t;void init()
{int cnt=1;for(int i=1;i<N;i++)for(int j=1;j<=i;j++){id[i][j]=cnt;p[cnt]=make_pair(i,j);cnt++;}
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();int w;cin>>w;while(w--){LL ans=0;scanf("%d",&n);t.init();for(int i=1;i<n;i++)for(int j=1;j<=i;j++){int w;scanf("%d",&w);ans+=w;t.addedge(id[i][j],id[i+1][j],w);t.addedge(id[i+1][j],id[i][j],w);}for(int i=1;i<n;i++)for(int j=1;j<=i;j++){int w;scanf("%d",&w);ans+=w;t.addedge(id[i][j],id[i+1][j+1],w);t.addedge(id[i+1][j+1],id[i][j],w);}for(int i=1;i<n;i++)for(int j=1;j<=i;j++){int w;scanf("%d",&w);ans+=w;t.addedge(id[i+1][j],id[i+1][j+1],w);t.addedge(id[i+1][j+1],id[i+1][j],w);}t.Dijkstra(id[1][1]);ans-=t.d[id[n][n]];t.dfs(id[1][1]);printf("%lld\n",ans);t.print();}return 0;
}
?
總結(jié)
以上是生活随笔為你收集整理的ZOJ - 4122 Triangle City(最短路+欧拉通路+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
