《算法竞赛进阶指南》------图论篇

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;
    else
    return 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");
    else
    printf("%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;
      else
        rep(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;
}