BZOJ2200: [Usaco2011 Jan]道路和航线

n<=25000个点m1<=50000条正权无向边m2<=50000条正负权有向边,保证有向边连接的无向边联通块形成一个拓扑图,求从s到每个点最短路。

第一次发现不会最短路。没看题乱写迪杰无脑WA,很好。迪杰从来不能处理负权最短路,然后就开始啃题解。。http://www.cnblogs.com/staginner/archive/2012/10/01/2709487.html这篇代码不错,讲得也很好。

在每个无向边联通块中找最短路可以直接迪杰。至于过度到不同的联通块,可以对无向图联通块形成的拓扑图按拓扑序来走。也就是说开一个队列记待搜集和每个集合在从前搜到的起点,在每次迪杰时利用并更新他们。

过程有点长,需组织完整后一气呵成!

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<algorithm>
  4 #include<math.h>
  5 //#include<iostream>
  6 #include<queue>
  7 using namespace std;
  8
  9 int n,m1,m2,s;
 10 #define maxn 25011
 11 #define maxm 100011
 12 const int inf=0x3f3f3f3f;
 13 struct Edge{int to,next,v;};
 14 struct qnode
 15 {
 16     int v,id;
 17     bool operator < (const qnode &b) const {return v<b.v;}
 18     bool operator > (const qnode &b) const {return v>b.v;}
 19 };
 20 int ufs[maxn];
 21 void ufsclear(int n)
 22 {
 23     for (int i=1;i<=n;i++) ufs[i]=i;
 24 }
 25 int find(int x) {return x==ufs[x]?x:(ufs[x]=find(ufs[x]));}
 26 void Union(int x,int y)
 27 {
 28     x=find(x),y=find(y);
 29     if (x==y) return;
 30     ufs[x]=y;
 31 }
 32 struct Graph
 33 {
 34     Edge road[maxm],fly[maxm];
 35     int froad[maxn],ffly[maxn],lr,lf;
 36     Graph()
 37     {
 38         memset(froad,0,sizeof(froad));
 39         memset(ffly,0,sizeof(ffly));
 40         lr=lf=2;
 41     }
 42     void in(Edge *edge,int *first,int &le,int x,int y,int v)
 43     {
 44         Edge &e=edge[le];
 45         e.to=y;e.v=v;
 46         e.next=first[x];
 47         first[x]=le++;
 48     }
 49     void insert(Edge *edge,int *first,int &le,int x,int y,int v)
 50     {
 51         in(edge,first,le,x,y,v);
 52         in(edge,first,le,y,x,v);
 53     }
 54     void in(int x,int y,int v) {in(fly,ffly,lf,x,y,v);}
 55     void insert(int x,int y,int v) {insert(road,froad,lr,x,y,v);}
 56     int deg[maxn];
 57     int que[maxn],head,tail;bool vis[maxn];
 58     void bfs()
 59     {
 60         que[head=(tail=1)-1]=s;
 61         vis[s]=1;
 62         memset(deg,0,sizeof(deg));
 63         while (head!=tail)
 64         {
 65             const int now=que[head++];
 66             for (int i=froad[now];i;i=road[i].next)
 67             {
 68                 Edge &e=road[i];
 69                 if (!vis[e.to]) vis[e.to]=1,que[tail++]=e.to;
 70             }
 71             for (int i=ffly[now];i;i=fly[i].next)
 72             {
 73                 Edge &e=fly[i];
 74                 deg[find(e.to)]++;
 75                 if (!vis[e.to]) vis[e.to]=1,que[tail++]=e.to;
 76             }
 77         }
 78     }
 79     Edge play[maxn];
 80     int fplay[maxn],lp;
 81     int dis[maxn];
 82     void inplay(int x,int y)
 83     {
 84         play[lp].to=y;
 85         play[lp].next=fplay[x];
 86         fplay[x]=lp++;
 87     }
 88     void dijkstra(int x)
 89     {
 90         priority_queue<qnode,vector<qnode>,greater<qnode> > q;
 91         for (int i=fplay[x];i;i=play[i].next)
 92         {
 93             Edge &e=play[i];
 94             q.push((qnode){dis[e.to],e.to});
 95             vis[e.to]=0;
 96         }
 97         while (!q.empty())
 98         {
 99             const int now=q.top().id,d=q.top().v;q.pop();
100             if (vis[now]) continue;
101             vis[now]=1;
102             for (int i=froad[now];i;i=road[i].next)
103             {
104                 Edge &e=road[i];
105                 if (dis[e.to]>d+e.v)
106                 {
107                     dis[e.to]=d+e.v;
108                     q.push((qnode){dis[e.to],e.to});
109                 }
110             }
111             for (int i=ffly[now];i;i=fly[i].next)
112             {
113                 Edge &e=fly[i];
114                 if (dis[e.to]>d+e.v)
115                 {
116                     dis[e.to]=d+e.v;
117                     if (!vis[e.to])
118                     {
119                         vis[e.to]=1;
120                         inplay(find(e.to),e.to);
121                     }
122                 }
123                 deg[find(e.to)]--;
124                 if (!deg[ufs[e.to]]) que[tail++]=ufs[e.to];
125             }
126         }
127     }
128     void solve()
129     {
130         bfs();
131         for (int i=1;i<=n;i++) dis[i]=inf;dis[s]=0;
132         memset(fplay,0,sizeof(fplay));lp=2;
133         que[head=(tail=1)-1]=find(s);
134         inplay(ufs[s],s);
135         memset(vis,0,sizeof(vis));
136         while (head!=tail)
137         {
138             const int now=que[head++];
139             dijkstra(now);
140         }
141         for (int i=1;i<=n;i++)
142             printf(dis[i]==inf?"NO PATH\n":"%d\n",dis[i]);
143     }
144 }g;
145 int x,y,v;
146 int main()
147 {
148     scanf("%d%d%d%d",&n,&m1,&m2,&s);
149     ufsclear(n);
150     for (int i=1;i<=m1;i++)
151     {
152         scanf("%d%d%d",&x,&y,&v);
153         g.insert(x,y,v);
154         Union(x,y);
155     }
156     for (int i=1;i<=m2;i++)
157     {
158         scanf("%d%d%d",&x,&y,&v);
159         g.in(x,y,v);
160     }
161     g.solve();
162     return 0;
163 }

时间: 08-29

BZOJ2200: [Usaco2011 Jan]道路和航线的相关文章

[Usaco2011 Jan]道路和航线

Description Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查.他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T.这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接.每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T),花费为C_i.对于道路,0

【BZOJ2199】[Usaco2011 Jan]奶牛议会 2-SAT

[BZOJ2199][Usaco2011 Jan]奶牛议会 Description 由于对Farmer John的领导感到极其不悦,奶牛们退出了农场,组建了奶牛议会.议会以“每头牛 都可以获得自己想要的”为原则,建立了下面的投票系统: M只到场的奶牛 (1 <= M <= 4000) 会给N个议案投票(1 <= N <= 1,000) .每只 奶牛会对恰好两个议案 B_i and C_i (1 <= B_i <= N; 1 <= C_i <= N)投 出“是

道路和航线

题目描述 Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查.他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T.这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接.每条道路i或者航线i连接城镇Ai (1 <= Ai <= T)到Bi (1 <= Bi <= T),花费为Ci.对于道路,0 <= Ci &l

AcWing 道路与航线

AcWing 道路与航线 Description Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查.他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T.这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接.每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T),

BZOJ 2200 道路与航线

好厉害呀这道题,有种豁然开朗的感觉.... 按拓扑顺序跑最短路. 然后注意细节,像WA的代码犯下的错是一笔带过没有丝毫考虑的...然而就是错了. 考试的时候一定要拍啊. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> #define

【BZOJ2199】 [Usaco2011 Jan]奶牛议会

Description 由于对Farmer John的领导感到极其不悦,奶牛们退出了农场,组建了奶牛议会.议会以“每头牛 都可以获得自己想要的”为原则,建立了下面的投票系统: M只到场的奶牛 (1 <= M <= 4000) 会给N个议案投票(1 <= N <= 1,000) .每只 奶牛会对恰好两个议案 B_i and C_i (1 <= B_i <= N; 1 <= C_i <= N)投 出“是”或“否”(输入文件中的'Y'和'N').他们的投票结果分别

BZOJ2199 [Usaco2011 Jan]奶牛议会

首先激励一个2-SAT的裸模型,然后发现...tarjan没法判断'?'的情况 于是暴力对每一个议案check一下,直接dfs即可 1 /************************************************************** 2 Problem: 2199 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:160 ms 7 Memory:884 kb 8 ********************

BZOJ 2199: [Usaco2011 Jan]奶牛议会 [2-SAT 判断解]

http://www.lydsy.com/JudgeOnline/problem.php?id=2199 题意:裸的2-SAT,但是问每个变量在所有解中是只能为真还是只能为假还是既可以为真又可以为假 这样的话求$SCC$的做法就不好做了 于是只能用$naive$做法了,枚举每个变量选择真假然后$dfs$一遍看看是否可行 #include <iostream> #include <cstdio> #include <cstring> #include <algori

ACwing 342. 道路与航线

首先看到这道题目,我们发现这道题目的复杂度,首先确定了是O(nlogn)O(nlogn)级别的,所以说,我们的算法初步确定在dijskra和SPFA上面. 但是我们发现这道题目一个关键点,就是题目中出现了负权边. 一旦出现了负权边,那么我们只能使用SPFA. 关于SPFA优化https://www.cnblogs.com/TFLS-gzr/p/10389141.html #include <bits/stdc++.h> using namespace std; const int N=4000