# BZOJ2200: [Usaco2011 Jan]道路和航线

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

```  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 {
36     Graph()
37     {
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);}
56     int deg[maxn];
58     void bfs()
59     {
61         vis[s]=1;
62         memset(deg,0,sizeof(deg));
64         {
67             {
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;
103             {
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;
134         inplay(ufs[s],s);
135         memset(vis,0,sizeof(vis));
137         {
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 }```

## [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)投 出“是

## 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),

## 【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').他们的投票结果分别

## 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