4.17题目总结(图论题目)

2018-04-17 16:43:23


POJ 1511 Invitation Cards

给定一张带正权的有向图,有n个人要从点1出发走到1..n的所有点,然 后再走回点1,求他们走过的所有路径长度和的最小值。

n, m ≤ 1000000,时限8s

解法:

经典最短路变形,分别建出正向边和反向边以1为源点跑最短路。

如果用Dijkstra的话,复杂度是O((n + m) log n)

假如常数太大,这样做有可能会超时。换用SPFA就能以很快的速度通过了。复杂度是O(玄学)。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e6+3;
const long long inf=0x7ffffffff;
int s=1,cnt1,cnt2,head1[N],head2[N],n,m,t;
ll d1[N],d2[N],ans;
struct tu{
    int to,ne;
    ll w;
}e1[N],e2[N];
inline void add1(int u,int v,ll w){
    cnt1++;
    e1[cnt1].to=v;
    e1[cnt1].w=w;
    e1[cnt1].ne=head1[u];
    head1[u]=cnt1;
}
inline void add2(int u,int v,ll w){
    cnt2++;
    e2[cnt2].to=v;
    e2[cnt2].w=w;
    e2[cnt2].ne=head2[u];
    head2[u]=cnt2;
}
queue<int>q;
bool inq[N];
void spfa1(){
    fill(d1+1,d1+n+1,inf);
    d1[s]=0;
    q.push(s);
    inq[s]=true;
    while(!q.empty()){
        int i = q.front();
        q.pop();
        inq[i]=false;
        for(int j = head1[i];j;j=e1[j].ne){
            int v=e1[j].to;
            if(d1[v]>d1[i]+e1[j].w){
                d1[v]=d1[i]+e1[j].w;
                if(!inq[v]){
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
}
void spfa2(){
    fill(d2+1,d2+n+1,inf);
    d2[s]=0;
    q.push(s);
    inq[s]=true;
    while(!q.empty()){
        int i = q.front();
        q.pop();
        inq[i]=false;
        for(int j = head2[i];j;j=e2[j].ne){
            int v=e2[j].to;
            if(d2[v]>d2[i]+e2[j].w){
                d2[v]=d2[i]+e2[j].w;
                if(!inq[v]){
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i = 1;i<=m;i++){
            int u,v;
            ll w;
            scanf("%d%d%lld",&u,&v,&w);
            add1(u,v,w);
            add2(v,u,w);
        }
        spfa1();
        spfa2();
        ans=0;
//      for(int i = 1;i<=n;i++){
//          printf("%lld ",d1[i]);
//      }
//      puts(" ");
//      for(int i = 1;i<=n;i++){
//          printf("%lld ",d2[i]);
//      }
//      puts(" ");
        for(int i = 1;i<=n;i++){
            ans+=d1[i]+d2[i];
        }
        printf("%lld\n",ans);
        memset(e1,0,sizeof(e1));
        memset(e2,0,sizeof(e2));
        memset(head1,0,sizeof(head1));
        memset(head2,0,sizeof(head2));
        memset(d1,0,sizeof(d1));
        memset(d2,0,sizeof(d2));
        cnt1=cnt2=0;
    }
    return 0;
}

POJ1062 昂贵的聘礼

有n件物品,你想要获得其中的物品1。每个物品都有个直接购买的价 格,你也有一定的金币,但不幸的是你的钱可能不够。还好,可以用 别的物品来换购;具体来说,每件物品i都有若干种(可能为0)换购方 式,表示如果你有某件其他物品j,那么用j加上额外的一些钱,就可以 买到i了。

此外,每件物品都有一个等级。你购买的任意两件物品的等级差都不 能超过一个给定的值m。求在这些条件下,要想买到物品1,最少需要 多少金币。

n ≤ 100,价格及等级均为不超过1e9的正整数

解法:

枚举所购买的物品中的最低等级,相应算出最高等级,然后只用这些 物品建图跑最短路。复杂度O(n^3)。


小K的农场

小K在MC里面建立很多很多的农场,总共n个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共m个),以下列三种形式描述:

农场a比农场b至少多种植了c个单位的作物,

农场a比农场b至多多种植了c个单位的作物,

农场a与农场b种植的作物数一样多。

但是,由于小K的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

输入输出格式 输入格式: 第一行包括两个整数 n 和 m,分别表示农场数目和小 K 记忆中的信息数目。

接下来 m 行:

如果每行的第一个数是 1,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

如果每行的第一个数是 2,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至多多种植了 c 个单位的作物。

如果每行的第一个数是 3,家下来有 2 个整数 a,b,表示农场 a 种植的数量和 b 一样多。

输出格式: 如果存在某种情况与小 K 的记忆吻合,输出“Yes”,否则输出“No”。

解法:

差分约束,没有负环即可

对于形如a-b<=c这样的式子,我们可以建立一条从b到a边权为c的有向边,然后先拓扑排序找出所有环,再对于每个环DFS一遍判断是不是负环即可。

这题我做的时候迷之多跑一遍bfs的spfa,后来观察数据发现用spfa的输出的都是Yes,于是又思考了一下,发现果然根本不用跑spfa

然后我又发现。。。根本不用拓扑排序

直接DFS!

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<climits>
using namespace std;
const int N = 1e5+3;
const int inf=INT_MAX;
int n,m,head[N],cnt;
int d[N];
struct tu{
    int to,ne,w;
}e[4*N+1];
void add(int u,int v,int w){
    cnt++;
    e[cnt].w=w;
    e[cnt].to=v;
    e[cnt].ne=head[u];
    head[u]=cnt;
}
//queue<int>q;
//bool inq[2*N+1];
//bool spfa(int s){
//  fill(d+1,d+n+1,inf);
//  d[s]=0;
//  q.push(s);
//  inq[s]=true;
//  while(!q.empty()){
//      int i = q.front();
//      q.pop();
//      inq[i]=false;
//      for(int j = head[i];j;j=e[j].ne){
//          int v = e[j].to;
//          if(d[v]>d[i]+e[j].w){
//              d[v]=d[i]+e[j].w;
//              if(!inq[v]){
//                  q.push(v);
//                  inq[v]=true;
//              }
//          }
//      }
//  }
//  return true;
//}
int in[N+1];
bool vis[N+1];
queue<int>p;
void topsort(){
    for(int i = 1;i<=n+1;i++){
        if(!in[i]) p.push(i);
    }
    while(!p.empty()){
        int i = p.front();
        vis[i]=1;   
        p.pop();
        for(int j = head[i];j;j=e[j].ne){
            int v = e[j].to;
            in[v]--;
            if(!in[v]) p.push(v);
        }
    }
}
bool ever[N+1];
bool dfs(int i){
    ever[i]=true;
    for(int j=head[i];j;j=e[j].ne){
        int v=e[j].to,dis=d[i]+e[j].w;
        if(vis[v]) continue;
        if(dis<d[v]){
            if(ever[v]) return true;
            d[v]=dis;
            if(dfs(v)) return true;
        }
    }
    ever[i]=false;
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    int x,a,b,c;
    for(int i = 1;i<=m;i++){
        scanf("%d",&x);
        if(x==1){
            scanf("%d%d%d",&a,&b,&c);
            //a-b>=c
            add(a,b,-c);
            in[b]++;
        }
        if(x==2){
            scanf("%d%d%d",&a,&b,&c);
            //a-b<=c;
            add(b,a,c);
            in[a]++;
        }
        if(x==3){
            scanf("%d%d",&a,&b);
            add(a,b,0);
            in[b]++;
            add(b,a,0);
            in[a]++;
        }
    }
    for(int i = 1;i<=n;i++){
        add(n+1,i,0);
        in[i]++;
    }
    topsort();
    for(int i = 1;i<=n+1;i++){
        if(!vis[i]){
            if(dfs(i)){
                puts("No");
                return 0;
            }
        }
    }
    //bool ans=spfa(n+1);
    //if(ans) 
    puts("Yes");
    //else printf("No\n");
    return 0;
}
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<climits>
using namespace std;
const int N = 1e5+3;
const int inf=INT_MAX;
int n,m,head[N],cnt;
int d[N];
struct tu{
    int to,ne,w;
}e[2*N+1];
void add(int u,int v,int w){
    cnt++;
    e[cnt].w=w;
    e[cnt].to=v;
    e[cnt].ne=head[u];
    head[u]=cnt;
}
bool ever[N+1];
bool dfs(int i){
    ever[i]=true;
    for(int j=head[i];j;j=e[j].ne){
        int v=e[j].to;
        if(d[i]+e[j].w<d[v]){
            if(ever[v]) return true;
            d[v]=d[i]+e[j].w;
            if(dfs(v)) return true;
        }
    }
    ever[i]=false;
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    int x,a,b,c;
    for(int i = 1;i<=m;i++){
        scanf("%d",&x);
        if(x==1){
            scanf("%d%d%d",&a,&b,&c);
            //a-b>=c
            add(a,b,-c);
        }
        if(x==2){
            scanf("%d%d%d",&a,&b,&c);
            //a-b<=c;
            add(b,a,c);
        }
        if(x==3){
            scanf("%d%d",&a,&b);
            add(a,b,0);
            add(b,a,0);
        }
    }
    for(int i = 1;i<=n;i++){
        add(n+1,i,0);
    }
    fill(d+1,d+n+2,inf);
    d[n+1]=0;
    if(dfs(n+1)){
        puts("No");
        return 0;
    }
    puts("Yes");
    return 0;
}