【强联通分量缩点】【最长路】【spfa】CH Round #59 - OrzCC杯NOIP模拟赛day1 队爷的讲学计划

浏览数：26 / 时间：2015年06月11日

10分算法：对于城市网络为一条单向链的数据，

20分算法：对于n<=20的数据，暴力搜出所有的可能路径。结合以上可以得到30分。

60分算法：分析题意可得使者会带着去的城市也就是这个城市所在强联通分量的其他城市，这个过程的代价也就是这个强联通分量的城市数-1，且他可以选择任何一个其中的城市离开这个强联通分量。于是我们求出所有强联通分量，记录下每一个包含的城市数，然后缩点。接下来再用dfs，由于数据是构造的，只能得到60分。

100分算法：在缩点之后，这个图变成了一个有向无环图，我们将一条边连向的SCC包含的城市数看做边权（<--其实一条边的边权是一个pair，pair.first为其连向的SCC包含的城市数；pair.second为原本的边权+其连向的SCC包含的城市数-1），这样问题就转化为了求一个有向无环图上的最长路径，利用DP或者Spfa或者其他的方法求解即可，本题没有构造卡Spfa的数据。

比赛的时候写的缩点+暴搜，被卡成60分。

//下划线为官方题解。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 #define M 500001
 7 #define N 100001
 8 struct Node
 9 {
10     int v,w;
11     Node(const int &a,const int &b){v=a;w=b;}
12     Node(){}
13 };
14 struct Edge
15 {
16     int u,v,w;
17     Edge(const int &a,const int &b,const int &c){u=a;v=b;w=c;}
18     Edge(){}
19 }edges[M];
20 vector<Node>ljb[M];
21 vector<int>vs,G[M],rG[M];
22 typedef vector<int>::iterator ITER;
23 typedef vector<Node>::iterator Edge_ITER;
24 int sum,n,m,x,y,z,anscity,cnt[N],cmp[N],anscost=2147483647;
25 bool vis[N];
26 void dfs(int U)
27 {
28     vis[U]=1;
29     for(ITER it=G[U].begin();it!=G[U].end();it++)
30       if(!vis[*it])
31         dfs(*it);
32     vs.push_back(U);
33 }
34 void rdfs(int U)
35 {
36     vis[U]=1;
37     cmp[U]=sum;
38     cnt[sum]++;
39     for(ITER it=rG[U].begin();it!=rG[U].end();it++)
40       if(!vis[*it])
41         rdfs(*it);
42 }
43 void scc()
44 {
45     for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
46     memset(vis,0,sizeof(vis));
47     ITER it=vs.end(); it--;
48     for(;;it--)
49       {
50           if(!vis[*it])
51           {
52               sum++;
53               rdfs(*it);
54           }
55           if(it==vs.begin()) break;
56       }
57 }
58 void dfs3(int U,int city,int cost)
59 {
60     if(city>anscity)
61       {
62           anscity=city;
63           anscost=cost;
64       }
65     else if(city==anscity && cost<anscost)
66       anscost=cost;
67     for(Edge_ITER it=ljb[U].begin();it!=ljb[U].end();it++)
68       dfs3((*it).v,city+cnt[(*it).v],cost+(*it).w+cnt[(*it).v]-1);
69 }
70 int main()
71 {
72     scanf("%d%d",&n,&m);
73     for(int i=1;i<=m;i++)
74       {
75           scanf("%d%d%d",&x,&y,&z);
76           G[x].push_back(y);
77           rG[y].push_back(x);
78           edges[i]=Edge(x,y,z);
79       }
80     scc();
81     for(int i=1;i<=m;i++)
82       if(cmp[edges[i].u]!=cmp[edges[i].v])
83         ljb[cmp[edges[i].u]].push_back(Node(cmp[edges[i].v],edges[i].w));
84     dfs3(cmp[1],cnt[cmp[1]],cnt[cmp[1]]-1);
85     printf("%d %d\n",anscity,anscost);
86     return 0;
87 }

后来写的缩点+spfa，要注意所谓的spfa最长路是双关键字比较的，优先让pair.first最大化，再让pair.second最小化，重载下运算符就可以了。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 #define INF 2147483647
  8 #define M 500001
  9 #define N 100001
 10 queue<int>q;
 11 struct Node
 12 {
 13     int v,w;
 14     Node(const int &a,const int &b){v=a;w=b;}
 15     Node(){}
 16 }dis[N];
 17 bool operator < (const Node &a,const Node &b)
 18 {return a.v!=b.v ? a.v<b.v : a.w>b.w;}
 19 Node operator + (const Node &a,const Node &b)
 20 {return Node(a.v+b.v,a.w+b.w);}
 21 struct Edge
 22 {
 23     int u,v,w;
 24     Edge(const int &a,const int &b,const int &c){u=a;v=b;w=c;}
 25     Edge(){}
 26 }edges[M];
 27 vector<Edge>ljb[M];
 28 vector<int>vs,G[M],rG[M];
 29 typedef vector<int>::iterator ITER;
 30 typedef vector<Edge>::iterator Edge_ITER;
 31 int sum,n,m,x,y,z,anscity,cnt[N],cmp[N],anscost=2147483647;
 32 Node ans;
 33 bool vis[N],inq[N];
 34 void dfs(int U)
 35 {
 36     vis[U]=1;
 37     for(ITER it=G[U].begin();it!=G[U].end();it++)
 38       if(!vis[*it]) dfs(*it);
 39     vs.push_back(U);
 40 }
 41 void rdfs(int U)
 42 {
 43     vis[U]=1; cmp[U]=sum; cnt[sum]++;
 44     for(ITER it=rG[U].begin();it!=rG[U].end();it++)
 45       if(!vis[*it]) rdfs(*it);
 46 }
 47 void scc()
 48 {
 49     for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
 50     memset(vis,0,sizeof(vis));
 51     ITER it=vs.end(); it--;
 52     for(;;it--)
 53       {
 54           if(!vis[*it])
 55           {
 56               sum++;
 57               rdfs(*it);
 58           }
 59           if(it==vs.begin()) break;
 60       }
 61 }
 62 void spfa(const int &s)//Node.v权最大化的城市数，Node.w权为最小化的cost 
 63 {
 64     for(int i=2;i<=sum;i++) dis[i]=Node(-INF,INF);
 65     dis[1]=Node(cnt[s],cnt[s]-1);
 66     inq[1]=1; ans=Node(-2147483647,2147483647);
 67     q.push(1);
 68     while(!q.empty())
 69       {
 70         int cur=q.front();
 71         for(Edge_ITER it=ljb[cur].begin();it!=ljb[cur].end();it++)
 72           if(dis[(*it).u]<dis[cur]+Node((*it).v,(*it).w))
 73             {
 74             dis[(*it).u]=dis[cur]+Node((*it).v,(*it).w);
 75             if(!inq[(*it).u])
 76               {
 77                 q.push((*it).u);
 78                 inq[(*it).u]=1;
 79               }
 80             }
 81         q.pop(); inq[cur]=0;
 82       }
 83     for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
 84     printf("%d %d\n",ans.v,ans.w);
 85 }
 86 int main()
 87 {
 88     scanf("%d%d",&n,&m);
 89     for(int i=1;i<=m;i++)
 90       {
 91           scanf("%d%d%d",&x,&y,&z);
 92           G[x].push_back(y);
 93           rG[y].push_back(x);
 94           edges[i]=Edge(x,y,z);
 95       }
 96     scc();
 97     for(int i=1;i<=m;i++)
 98       if(cmp[edges[i].u]!=cmp[edges[i].v])
 99         ljb[cmp[edges[i].u]].push_back(Edge(cmp[edges[i].v],cnt[cmp[edges[i].v]],edges[i].w+cnt[cmp[edges[i].v]]-1));
100     spfa(1);
101     return 0;
102 }