poj3114&3110-强连通图targan+spfa

悠悠 2022-07-12 02:44 160阅读 0赞

强连通图： 在一个有向图中，所有顶点都能互相到达则为强连通图

强连通分量：对于一个有向非强连通图的一个子图强连通，则这个子图称为强连通分量

targan：用于求有向图强连通分量的算法，该算法基于对图的dfs，即每个强连通分量为dfs的一颗子树

即从某一个顶点开始往下dfs并且把点入栈，如果走到不能走时，说明以改点是一个强连通分量

如果下一个节点已经在栈中，说明存在一个强连通分量，然后回溯，当回溯到那个点时，此时在

栈中位于改点之上的点为一个强连通分量！

算法实现：我们定义数组 dfn\[i\]为i点在dfs当中的编号即时间戳，low\[i\]为i点在子树中能到达的最小的编号，

所以当dfn\[i\]==low\[i\]时说明当前存在一个强连通分量

具体可以参见博客：[targan算法有向图强连通分量][targan]

算法例子：

1，poj3114

Countries in War

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;3816</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;1109</td> 
  </tr> 
 </tbody> 
</table>

Description

In the year 2050, after different attempts of the UN to maintain peace in the world, the third world war broke out. The importance of industrial, commercial and military secrets obliges all the countries to use extremely sophisticated espionage services, so that each city in the world has at least one spy of each country. These spies need to communicate with other spies, informers as well as their headquarters during their actions. Unluckily there doesn’t exist a secure way for a spy to communicate during the war period, therefore the messages are always sent in code so that only the addressee is able to read the message and understand its meaning.

The spies use the only service that functions during the war period, the post. Each city has a postal agency where the letters are sent. The letters can be sent directly to their destination or to other postal agencies, until the letter arrives at the postal agency of the destination city, if possible.

The postal agency in city A can send a printed letter to the postal agency in city B if there is an agreement on sending letters, which determines the time, in hours, that a letter takes to reach city B from city A (and not necessarily the opposite). If there is no agreement between the agencies A and B, the agency A can try to send the letter to any agency so that the letter can reach its destination as early as possible

Some agencies are connected with electronic communication media, such as satellites and optical fibers. Before the war, these connections could reach all the agencies, making that a letter could be sent instantly. But during the period of hostilities every country starts to control electronic communication and an agency can only send a letter to another agency by electronic media (or instantly) if they are in the same country. Two agencies, A and B, are in the same country if a printed letter sent from any one of the agencies can be delivered to the other one.

The espionage service of your country has managed to obtain the content of all the agreements on sending messages existing in the world and desires to find out the minimum time to send a letter between different pairs of cities. Are you capable of helping them?

Input

The input contains several test cases. The first line of each test case contains two integer separated by a space, *N* (1 ≤ *N* ≤ 500) and *E* (0 ≤ *E* ≤ *N*2), indicating the numbers of cities (numbered from 1 to *N*) and of agreements on sending messages, respectively. Following them, then, *E* lines, each containing three integers separated by spaces, *X*, *Y* and *H* (1 ≤ *X*, *Y* ≤ *N*, 1 ≤ *H* ≤ 1000), indicating that there exist an agreement to send a printed letter from city *X* to city *Y*, and that such a letter will be delivered in *H* hours.

After that, there will be a line with an integer *K* (0 ≤ *K* ≤ 100), the number of queries. Finally, there will be *K* lines, each representing a query and containing two integers separated by a space, *O*and *D* (1 ≤ *O*, *D* ≤ *N*). You must determine the minimum time to send a letter from city *O* to city *D*.

The end of the input is indicated by *N* = 0.

Output

For each test case your program should produce *K* lines of output. The *I*\-th line should contain an integer *M*, the minimum time, in hours, to send a letter in the *I*\-th query. If there aren’t communication media between the cities of the query, you should print “Nao e possivel entregar a carta” (“It’s impossible to deliver the letter”).

Print a blank line after each test case.

Sample Input

4 5
    1 2 5
    2 1 10
    3 4 8
    4 3 7
    2 3 6
    5
    1 2
    1 3
    1 4
    4 3
    4 1
    3 3
    1 2 10
    2 3 1
    3 2 1
    3
    1 3
    3 1
    3 2
    0 0

Sample Output

0
    6
    6
    0
    Nao e possivel entregar a carta
    
    10
    Nao e possivel entregar a carta
    0

Source

[South America 2006][], Brazil Subregion

题目思路：

给你一张n个点，m条边的有向图和k询问，每次询问从u到v的最短路，对于图中，强连通分量中的点的距离为0

所以我们可以先用targan缩点，即一个强连通分量缩成一个点，然后重新建图即可

AC代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    
    using namespace std;
    
    const int maxn = 550;
    const int inf = 1e8;
    
    struct st{
        int v,w,nex;
    }tedge[maxn*maxn],edge[maxn*maxn];
    
    int n,m,e,index,cnt,top;
    int hed[maxn],thed[maxn],dis[maxn],vis[maxn];
    int dfn[maxn],low[maxn],stack[maxn],belon[maxn];
    
    void init(){
        memset(hed,-1,sizeof(hed));
        memset(thed,-1,sizeof(hed));
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        e=1;index=top=cnt=0;
    }
    
    void tadd(int u,int v,int w){
        tedge[e].v=v,tedge[e].w=w,tedge[e].nex=thed[u],thed[u]=e++;
    }
    
    void add(int u,int v,int w){
        edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;
    }
    
    void targan(int i){
        dfn[i]=low[i]=++index;
        stack[top++]=i;
        vis[i]=1;
        for(int j=thed[i];~j;j=tedge[j].nex){
            int v = tedge[j].v;
            if(!dfn[v]){
                targan(v);
                if(low[v]<low[i])low[i]=low[v];
            }else if(vis[v]){
                if(dfn[v]<low[i])low[i]=dfn[v];
            }
        }
        if(low[i]==dfn[i]){
            cnt++;
            int j;
            do{
                j = stack[--top];
                belon[j]=cnt;
                vis[j]=0;
            }while(j!=i);
        }
    }
    
    void spfa(int u){
        for(int i=1;i<=n;i++)
            dis[i]=inf,vis[i]=0;
        dis[u]=0;
        priority_queue<pair<int,int> >q;
        q.push(make_pair(-dis[u],u));
        while(!q.empty()){
            int u = q.top().second;q.pop();
            if(vis[u])continue;
            vis[u]=1;
            for(int i=hed[u];~i;i=edge[i].nex){
                int v = edge[i].v;
                if(dis[v]>dis[u]+edge[i].w){
                    dis[v]=dis[u]+edge[i].w;
                    if(!vis[v]){
                        q.push(make_pair(-dis[v],v));
                    }
                }
            }
        }
    }
    
    int main()
    {
        while(cin>>n>>m,n+m){
            init();
            while(m--){
                int u,v,w;scanf("%d%d%d",&u,&v,&w);
                tadd(u,v,w);
            }
            for(int i=1;i<=n;i++){
                if(!dfn[i])targan(i);
            }
            e=1;
            for(int i=1;i<=n;i++){
                for(int j=thed[i];~j;j=tedge[j].nex){
                    int v = tedge[j].v;
                    if(belon[i]!=belon[v])add(belon[i],belon[v],tedge[j].w);
                }
            }
            int k;scanf("%d",&k);
            while(k--){
                int u,v;scanf("%d%d",&u,&v);
                if(belon[u]==belon[v]){
                    printf("0\n");
                    continue;
                }
                spfa(belon[u]);
                if(dis[belon[v]]==inf)printf("Nao e possivel entregar a carta\n");
                else printf("%d\n",dis[belon[v]]);
            }
            printf("\n");
        }
    
        return 0;
    }

poj3160：

Father Christmas flymouse

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;3303</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;1120</td> 
  </tr> 
 </tbody> 
</table>

Description

After retirement as contestant from WHU ACM Team, flymouse volunteered to do the odds and ends such as cleaning out the computer lab for training as extension of his contribution to the team. When Christmas came, flymouse played Father Christmas to give gifts to the team members. The team members lived in distinct rooms in different buildings on the campus. To save vigor, flymouse decided to choose only one of those rooms as the place to start his journey and follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms.

During the days on the team, flymouse left different impressions on his teammates at the time. Some of them, like LiZhiXu, with whom flymouse shared a lot of candies, would surely sing flymouse’s deeds of generosity, while the others, like snoopy, would never let flymouse off for his idleness. flymouse was able to use some kind of comfort index to quantitize whether better or worse he would feel after hearing the words from the gift recipients (positive for better and negative for worse). When arriving at a room, he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence. He could arrive at a room more than once but never enter it a second time. He wanted to maximize the the sum of comfort indices accumulated along his journey.

Input

The input contains several test cases. Each test cases start with two integers *N* and *M* not exceeding 30 000 and 150 000 respectively on the first line, meaning that there were *N* team members living in *N* distinct rooms and *M* direct paths. On the next *N* lines there are *N* integers, one on each line, the *i*\-th of which gives the comfort index of the words of the team member in the *i*\-th room. Then follow *M* lines, each containing two integers *i* and *j* indicating a directed path from the *i*\-th room to the *j*\-th one. Process to end of file.

Output

For each test case, output one line with only the maximized sum of accumulated comfort indices.

Sample Input

2 2
    14
    21
    0 1
    1 0

Sample Output

Hint

32-bit signed integer type is capable of doing all arithmetic.

Source

[POJ Monthly--2006.12.31][], Sempr

题目思路：

给你一张n点m条边的有向图，以及每个点的权值可以为负的，求从某一个点出发沿着给出的边一直走直到不能

走为止的最大权值，即最长路，对于一个点来说，你可以获得权值最多一次，但可以经过多次，所以我们可以忽略掉负值

应为存在强连通分量即有环，所以我们可以先用targan缩点，因为可能存在多个图，所以我们建一个超级原点0

这样我们就可以从0点跑一遍spfa最长路即可

AC代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    
    using namespace std;
    
    const int maxn = 3e4+100;
    const int inf = 1e9;
    
    struct st{
        int v,w,nex;
    }tedge[maxn*10],edge[maxn*10];
    
    int n,m,e,index,cnt,top;
    int hed[maxn],thed[maxn],dis[maxn],vis[maxn],out[maxn];
    int dfn[maxn],low[maxn],stack[maxn],belon[maxn],tw[maxn],w[maxn];
    
    void init(){
        memset(hed,-1,sizeof(hed));
        memset(thed,-1,sizeof(hed));
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        memset(w,0,sizeof(w));
        e=1;index=top=cnt=0;
    }
    
    void tadd(int u,int v){
        tedge[e].v=v,tedge[e].nex=thed[u],thed[u]=e++;
    }
    
    void add(int u,int v,int w){
        edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;
    }
    
    void targan(int i){
        dfn[i]=low[i]=++index;
        stack[top++]=i;
        vis[i]=1;
        for(int j=thed[i];~j;j=tedge[j].nex){
            int v = tedge[j].v;
            if(!dfn[v]){
                targan(v);
                if(low[v]<low[i])low[i]=low[v];
            }else if(vis[v]){
                if(dfn[v]<low[i])low[i]=dfn[v];
            }
        }
        if(low[i]==dfn[i]){
            cnt++;
            int j;
            do{
                j = stack[--top];
                belon[j]=cnt;
                vis[j]=0;
                if(tw[j]>0)w[cnt]+=tw[j];
            }while(j!=i);
        }
    }
    
    int spfa(){
        int ans = 0;
        queue<int>q;
        for(int i=0;i<=cnt;i++)dis[i]=0;
        q.push(0);
        while(!q.empty()){
            int u = q.front();q.pop();
            vis[u]=0;
            for(int i=hed[u];~i;i=edge[i].nex){
                int v = edge[i].v;
                if(dis[v]<dis[u]+edge[i].w){
                    dis[v]=dis[u]+edge[i].w;
                    if(!vis[v]){
                        q.push(v);
                         vis[v]=1;
                    }
                }
            }
        }
        for(int i=1;i<=cnt;i++)
            if(!out[i])ans=max(ans,dis[i]);
        return ans;
    }
    
    int main()
    {
        while(cin>>n>>m){
            init();
            for(int i=1;i<=n;i++)scanf("%d",&tw[i]);
            while(m--){
                int u,v;scanf("%d%d",&u,&v);
                u++,v++;
                tadd(u,v);
            }
            for(int i=1;i<=n;i++){
                if(!dfn[i])targan(i);
            }
            e=0;
            int in[maxn];
            memset(in,0,sizeof(in));
            memset(out,0,sizeof(out));
            for(int i=1;i<=n;i++){
                for(int j=thed[i];~j;j=tedge[j].nex){
                    int v = tedge[j].v;
                    if(belon[i]!=belon[v]){
                        in[belon[v]]++;
                        out[belon[i]]++;
                        add(belon[i],belon[v],w[belon[v]]);
                    }
                }
            }
            for(int i=1;i<=cnt;i++){
                if(!in[i]){
                    add(0,i,w[i]);
                }
            }
            printf("%d\n",spfa());
        }
        return 0;
    }

[targan]: http://blog.csdn.net/wsniyufang/article/details/6604458
[South America 2006]: http://poj.org/searchproblem?field=source&key=South+America+2006
[POJ Monthly--2006.12.31]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2006.12.31