《算法競賽進階指南》------圖論篇

文章目錄

- 0x01 Telephone Lines POJ - 3662
- 0x02 P1073 [NOIP2009 提高組] 最優貿易
- 0x03 道路和航線 BZOJ2200
- 0x04 Sorting It All Out POJ - 1094 topo
- 0x05 Sightseeing trip POJ - 1734 最小環問題
- 0x06 Cow Relays POJ - 3613 S到E經過k條邊的最短路
- 0x07 走廊潑水節（Kruskal）

0x01 Telephone Lines POJ - 3662

Telephone Lines
題意：從1到N修一條電纜，有p對電線桿之間是可以連接的，電信公司可以提供k條電纜，其他的由John提供，求john提供的電纜的最長的那根的長度（ret）。
思路：實則是求最短最長的邊。
二分結果(sum)。對于邊值>sum, 電信公司需要提供電纜。
用djk 計算 1->n 路徑上的最短路徑。滿足d[n]< k ，sum是一個符合的結果。
代碼如下：

#include<iostream>
#include<cstring>
#include<queue>
#define ll long long
#define ld long double
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
ll gcd(ll a,ll b){ return b? gcd(b,a%b):a;}
const int N=2e4+10;
const ll P=1e9+7;
ll read(){ll s = 0, f = 1; char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();return s * f;
}
using namespace std;
ll n,p,k;
ll head[N],ver[N],nex[N],edgevalue[N];
ll cnt;
void addedge(ll u,ll v,ll value)
{ver[++cnt]=v;edgevalue[cnt]=value;nex[cnt]=head[u];head[u]=cnt;
}
priority_queue<pair<int,int>> q;
ll d[N],v[N];
bool ischeck(ll sum)
{memset(d,0x3f,sizeof(d));memset(v,0,sizeof(v));while(!q.empty()){q.pop();}d[1]=0;q.push(make_pair(0,1));  //  距離  點while(!q.empty()){ll x=q.top().second;q.pop();if(v[x]) continue;v[x]=1;for(int i=head[x];i;i=nex[i]){int y=ver[i],z=edgevalue[i];if(z> sum)  z=1;else z=0;if(d[y]>d[x]+z){d[y]=d[x]+z;q.push(make_pair(-d[y],y));}}if(v[n]==1) break;}// printf("%lld\n",d[n]);// getchar();if(d[n]<=k) return true;elsereturn false;
}
void solve(){n=read();p=read();k=read();ll u,v,value;rep(i,1,p){u=read();v=read();value=read();addedge(u,v,value);addedge(v,u,value);        }ll l=0,r=1000010;ll mid;while(l<r){mid=(l+r)>>1;// printf("l:%lld r:%lld mid:%lld\n",l,r,mid);if(ischeck(mid)){r=mid;}else{l=mid+1;}}if(r==1000010) printf("-1\n");elseprintf("%lld\n",r);return ;
}
int main (){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);solve();getchar();getchar();return 0;
}

0x02 P1073 [NOIP2009 提高組] 最優貿易

最優貿易
題意：從1到達n號，在沿途中可選一點購買水晶球，在此之后可賣出去水晶球。商人阿龍只能購買一次，
問商人阿龍旅游結束后，通過這樣的方式最多賺取多少旅費？途中一座城市可被重復經過。
數據范圍： $1<=n<=10^5,1<=m<=5*10^5$
思路：
在這里插入圖片描述
代碼如下：

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
ll gcd(ll a,ll b){ return b? gcd(b,a%b):a;}
const int N=1e6+10;
const ll P=1e9+7;
ll read(){ll s = 0, f = 1; char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();return s * f;
}
using namespace std;
ll n,m;
ll vVAlue[N];
ll head[N],nex[N],ver[N];
ll cnt;
ll addedge(ll u,ll v)
{ver[++cnt]=v;nex[cnt]=head[u];head[u]=cnt;   
}ll vis[N];
void djk(ll u,ll *D,ll flag)
{     priority_queue< pair<int,int> > q;memset(vis,0,sizeof(vis));if(flag==1)rep(i,1,n) D[i]=200;elserep(i,1,n) D[i]=0;//    rep(i,1,n)  cout<<D[i]<<" "; cout<<endl;D[u]=vVAlue[u];q.push(make_pair(D[u],u));while(!q.empty()){ll x=q.top().second;q.pop();for(int i=head[x];i;i=nex[i]){   //   cout<<"321"<<endl;ll y=ver[i];if(flag==1){if(D[y] > D[x]){   // cout<<vVAlue[y]<<" "<<D[x]<<endl;D[y]=min(vVAlue[y],D[x]);q.push(make_pair(-D[y],y));}}else {if(D[y] < D[x]){   //cout<<vVAlue[y]<<" "<<D[x]<<endl;D[y]=max(vVAlue[y],D[x]);q.push(make_pair(D[y],y));}}  }}//   cout<<flag<<endl;//   rep(i,1,n)//   {//       printf("u:%lld  value:%lld\n",i,D[i]);//   }return ;
}
struct zw
{ll x,y,z;
}a[N];
ll D[N],F[N];
void solve(){n=read();m=read();rep(i,1,n) vVAlue[i]=read();ll x,y,z;rep(i,1,m){a[i].x=read();a[i].y=read();a[i].z=read();addedge(a[i].x,a[i].y);if(a[i].z==2){addedge(a[i].y,a[i].x);}}djk(1,D,1);cnt=0;memset(head,0,sizeof(head));rep(i,1,m){addedge(a[i].y,a[i].x);if(a[i].z==2){addedge(a[i].x,a[i].y);}}djk(n,F,-1);ll sum=0;rep(i,1,n) sum=max(sum,F[i]-D[i]);printf("%lld\n",sum);return ;
}
int main (){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);solve();getchar();getchar();return 0;
}

0x03 道路和航線 BZOJ2200

拓撲排序，djk，
道路和航線
題意：
在這里插入圖片描述思路：

代碼如下：

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
ll gcd(ll a,ll b){ return b? gcd(b,a%b):a;}
const int N=2e5+10;
// const ll P=1e9+7;
ll read(){ll s = 0, f = 1; char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();return s * f;
}
using namespace std;
ll n,R,P,S;
ll  cnt;
ll head[N],nex[N],edgevalue[N],var[N];
ll D[N],vis[N];
ll num[N],in[N];
ll ans;   // 編號個數
queue<int> c;  //存放編號
priority_queue< pair<ll,int>> q;
void addedge(ll u,ll v,ll value)
{var[++cnt]=v;edgevalue[cnt]=value;nex[cnt]=head[u];head[u]=cnt;
}
void dfs(ll u)
{   num[u]=ans;for(int i=head[u];i;i=nex[i]){int v=var[i];if(num[v]) continue;dfs(v);}return ;
}
void  djk(ll s)
{     ll u,v,value;memset(D,0x7f,sizeof(D));memset(vis,0,sizeof(vis));D[s]=0;c.push(num[s]);rep(i,1,ans){if(in[i]==0 and num[s]!=i)c.push(i);}while(!c.empty()){ll x=c.front();c.pop();rep(i,1,n){if(num[i]==x) q.push(make_pair(-D[i],i));}while(!q.empty()){u=q.top().second;q.pop();if(vis[u])  continue;vis[u]=1;for(int i=head[u];i;i=nex[i]){v=var[i];value=edgevalue[i];if(D[v] > D[u]+value){D[v]=D[u]+value;if(num[u]==num[v]){q.push(make_pair(-D[v],v));}}if(num[u]!=num[v]){   in[num[v]]--;if(in[num[v]]==0){c.push(num[v]);}} }}}
}
void solve(){n=read();R=read();P=read();S=read();ll u,v,value;rep(i,1,R){u=read(); v=read(); value=read();addedge(u,v,value);addedge(v,u,value);}rep(i,1,n){if(num[i]==0){ans++;dfs(i);}}rep(i,1,P){u=read();v=read();value=read();in[num[v]]++;addedge(u,v,value);}djk(S);rep(i,1,n){if(D[i]>0x3f3f3f3f) printf("NO PATH\n");else printf("%lld\n",D[i]);}return ;
}
int main (){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);solve();getchar();getchar();return 0;
}

0x04 Sorting It All Out POJ - 1094 topo

Sorting It All Out
題意：
在這里插入圖片描述
思路：

代碼如下：

#include<iostream>
#include<cstring>
#include<queue>
#define ll long long
#define ld long double
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
ll gcd(ll a,ll b){ return b? gcd(b,a%b):a;}
const int N=30;
const ll P=1e9+7;
ll read(){ll s = 0, f = 1; char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();return s * f;
}
using namespace std;
ll n,m,cnt;
ll in[N],in1[N];
ll head[N],var[1000],nex[1000];
void addedge(ll u,ll v)
{var[++cnt]=v;nex[cnt]=head[u];head[u]=cnt;
}
ll ans=0;
char ch[N];
ll topo()
{rep(i,0,n-1) in[i]=in1[i];ans=0;queue<int> q;rep(i,0,n-1){if(in[i]==0)  q.push(i);}bool logo=true;ll u,v;while(!q.empty()){if(q.size()>1) logo=false;ll u=q.front();ch[ans++]=u;q.pop();for(int i=head[u];i;i=nex[i]){v=var[i];if((--in[v])==0) q.push(v);} }// cout<<ans<<" "<<logo<<n<<endl;if(ans<n) return -1;else {if(logo==true) return 1;else return 0;}
}
void solve(){while(1){n=read();m=read();if(n==0 and m==0) break;rep(i,0,n){in1[i]=0;head[i]=0;cnt=0;}char x,y;ll u,v;ll res=0;ll inde=0;rep(i,1,m){cin>>x>>y>>y;u=x-'A';v=y-'A';addedge(u,v);in1[v]++;if(res==0){res=topo();// cout<<res<<endl;inde=i;} }// cout<<res<<endl;if(res==0) cout<<"Sorted sequence cannot be determined."<<endl;else if(res==-1) cout<<"Inconsistency found after "<<inde<<" relations."<<endl;else if(res==1) {cout<<"Sorted sequence determined after "<<inde<<" relations: ";rep(i,0,ans-1)  printf("%c",ch[i]+'A');cout<<"."<<endl;}}
}
int main (){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);solve();getchar();getchar();return 0;
}

0x05 Sightseeing trip POJ - 1734 最小環問題

留下一個小疑問點： int 和 ll a=0x3f3f3f3f 在這道題中使用ll a=0x3f3f3f3f 會錯。
Sightseeing trip
題意：
在這里插入圖片描述
思路：弗洛伊德，回溯路徑。
外層循環k開始，對所以的路徑刷新，添上k和步添上k
這個算法的思想很關鍵

在這里插入圖片描述

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N=300+10;
using namespace std;
int a[N][N],dist[N][N],pos[N][N];
ll n,m;
ll ans=1e8;
vector<int> path;
void get_path(int x,int y){if(pos[x][y]==0) return ;get_path(x,pos[x][y]);path.push_back(pos[x][y]);get_path(pos[x][y],y);
}
void solve(){cin>>n>>m;//  memset(a,0x3f,sizeof(a));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=1e8;}}for(int i=0;i<=n;i++) a[i][i]=0;for(int i=1;i<=m;i++){   int u,v,w;cin>>u>>v>>w;a[u][v]=a[v][u]=min(a[u][v],w);}memcpy(dist,a,sizeof(a));for(int k=1;k<=n;k++){for(int i=1;i<k;i++){for(int j=i+1;j<k;j++){if(dist[i][j]+a[j][k]+a[k][i]<ans){ans=dist[i][j]+a[j][k]+a[k][i];path.clear();path.push_back(i);get_path(i,j);path.push_back(j);path.push_back(k);}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(dist[i][j]> dist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];pos[i][j]=k;}}}}if(ans == 1e8){cout << "No solution." << endl;}else {for(int i=0;i<(int)path.size();i++){cout<<path[i]<<" ";}}return ;
}
int main (){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);solve();getchar();getchar();return 0;
}

0x06 Cow Relays POJ - 3613 S到E經過k條邊的最短路

傳送門
題意：
在這里插入圖片描述
思路: 點編號映射，矩陣快速冪
代碼如下：

#include<iostream>
#include<cstring>
#define ll long long
#define ld long double
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
ll gcd(ll a,ll b){ return b? gcd(b,a%b):a;}
const int N=2e5+10;
const ll P=1e9+7;
const ll INF=0x3f3f3f3f;
ll read(){ll s = 0, f = 1; char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();return s * f;
}
using namespace std;
ll  p[1010];
ll  a[300];
ll cnt;
struct M{ll edge[210][210];void init(){rep(i,1,200){rep(j,1,200){edge[i][j]=INF;                }}}
};
M add(M a,M b){M sum;sum.init();rep(i,1,cnt){rep(j,1,cnt){rep(k,1,cnt){sum.edge[i][j]=min(sum.edge[i][j],a.edge[i][k]+b.edge[k][j]);}}}return sum;
}
void solve(){ll n,t,s,e;cin>>n>>t>>s>>e;ll w,u,v;M sum;sum.init();for(int i=1;i<=t;i++){cin>>w>>u>>v;if(!p[u]){p[u]=(++cnt);a[cnt]=u;}if(!p[v]){p[v]=(++cnt);a[cnt]=v;}sum.edge[p[u]][p[v]]=min(w, sum.edge[p[u]][p[v]]);sum.edge[p[v]][p[u]]=min(w, sum.edge[p[v]][p[u]]);}M ans;memcpy(ans.edge,sum.edge,sizeof(sum.edge));// sum=add(sum,sum);n--;while(n){if(n&1) ans=add(ans,sum);sum=add(sum,sum);n>>=1;}cout<<ans.edge[p[s]][p[e]]<<endl;
}
int main (){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);solve();getchar();getchar();return 0;
}

0x07 走廊潑水節（Kruskal）

走廊潑水節
題意：
在這里插入圖片描述
思路：克里斯特+模擬

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
ll gcd(ll a,ll b){ return b? gcd(b,a%b):a;}
const int N=1e4+10;
const ll P=1e9+7;
ll read(){ll s = 0, f = 1; char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();return s * f;
}
using namespace std;
ll fa[N];
ll num[N];
ll  getfa(ll x){return x==fa[x] ? x: fa[x]=getfa(fa[x]);
}
struct zw{int x,y,z;
}a[N];
bool operator <(zw a,zw b){return a.z<b.z;
}
void solve(){ll n;cin>>n;rep(i,1,n-1){cin>>a[i].x>>a[i].y>>a[i].z;}rep(i,1,n){fa[i]=i;num[i]=1;}sort(a+1,a+n);ll sum=0;for(int i=1;i<=n-1;i++){int x=getfa(a[i].x);int y=getfa(a[i].y);if(x==y) continue;sum+=( num[x]*num[y]-1 )*(a[i].z+1);fa[y]=x;num[x]+=num[y];}cout<<sum<<endl;return ;
}
int main (){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T=read();while(T--)solve();getchar();getchar();return 0;
}