1001 : 点双连通分量：
tarjan模板题：需要注意的是，点双连通分量是极大子图，也就是说他如果是很多个环拼成一个环，那么这个分量还是一个，就是最大的那个。
我们从环顶退栈即可，类似割点的位置。
/ Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 2e5 + 5;
const int M = 2e3 + 5;
const LL Mod = 100000007;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
int n,m,dfn[N],low[N],tim = 0,cnt = 0;
vector<int> G[N];
stack<int> S;
void tarjan(int u,int fa) {
dfn[u] = low[u] = ++tim;
S.push(u);
for(auto v : G[u]) {
if(!dfn[v]) {
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u]) {
++cnt;
while(S.top() != v) S.pop();
}
}
else if(v != fa) low[u] = min(low[u],dfn[v]);
}
}
int main() {
scanf("%d %d",&n,&m);
while(m--) {
int x,y;scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
tarjan(1,0);
printf("%d\n",cnt);
// system("pause");
return 0;
}
/*
4 5
1 2
1 3
1 4
2 3
3 4
*/
View Code
1002 : Play on Words：
这里一开始忘记判断连通图了所以一直wa。
首先我们可以把每个单词看成连u -> v的一条有向边。
那么就是题目就是问是否存在一条欧拉通路。
条件就是：所有点的入度 = 出度，或者只存在一个点满足入度 - 出度 = 1 and 出度 - 入度 = 1
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 2e5 + 5;
const int M = 2e3 + 5;
const LL Mod = 100000007;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
int fa[30],in[30],out[30];
bool vis[30];
int Find(int x) {
return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
int main() {
int ca;scanf("%d",&ca);
while(ca--) {
int n;scanf("%d",&n);
for(int i = 0;i <= 25;++i) fa[i] = i,in[i] = out[i] = 0;
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;++i) {
string s;cin >> s;
int x = s[0] - 'a',y = s[s.size() - 1] - 'a';
vis[x] = vis[y] = 1;
if(x != y) {
in[x]++,out[y]++;
int xx = Find(x),yy = Find(y);
fa[xx] = yy;
}
}
int cnt = 0,tag1 = 0,tag2 = 0;
for(int i = 0;i <= 25;++i) {
if(vis[i] == 0) continue;
if(fa[i] == i) cnt++;
if(in[i] != out[i]) {
if(in[i] - out[i] == 1) tag1++;
else if(out[i] - in[i] == 1) tag2++;
else cnt = 2;
}
}
if(cnt > 1 || tag1 > 1 || tag2 > 1) printf("The door cannot be opened.\n");
else printf("Ordering is possible.\n");
}
// system("pause");
return 0;
}
View Code
1003 : Currency Exchange：
一开始的思路有点问题，直接认为第二次走到这个点比上一次更优就是在正权值环里了，但是有可能第二次是从另一条路过来的，值比上一次大。
所有还是慢慢松弛到比原来大比较好，优先队列会掉到无限环里，所以spfa松弛就可以了。
// Author: levil
#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
#include<stack>
#include<map>
#include<limits.h>
#include<vector>
#include<string.h>
#include<string>
using namespace std;
typedef long long LL;
typedef pair<double,int> pii;
const int N = 105;
const int M = 1e3 + 5;
const LL Mod = 100000007;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
int n,m,s,tot = 0,head[N];
bool vis[N];
double dp[N],V;
struct Node{int to,next;double r,c;}e[M << 1];
void init() {
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
tot = 0;
}
void add(int u,int v,double r,double c) {
e[++tot].to = v,e[tot].r = r,e[tot].c = c,e[tot].next = head[u],head[u] = tot;
}
bool solve() {
for(int i = 1;i <= n;++i) dp[i] = 0;
queue<int> Q;
dp[s] = V;
vis[s] = 1;
Q.push(s);
while(!Q.empty()) {
int u = Q.front();
vis[u] = 0;
Q.pop();
for(int i = head[u];i;i = e[i].next) {
int v = e[i].to;
double ma = (dp[u] - e[i].c) * e[i].r;
//printf("v is %d ma is %.2f\n",v,ma);
if(dp[v] < ma) {
dp[v] = ma;
if(dp[s] > V) return true;
if(vis[v] == 0) {
Q.push(v);
vis[v] = 1;
}
}
}
}
return false;
}
int main() {
while(~scanf("%d %d %d %lf",&n,&m,&s,&V)) {
init();
while(m--) {
int u,v;
double r1,c1,r2,c2;
scanf("%d %d %lf %lf %lf %lf",&u,&v,&r1,&c1,&r2,&c2);
add(u,v,r1,c1);
add(v,u,r2,c2);
}
printf("%s\n",solve() ? "YES" : "NO");
}
//system("pause");
return 0;
}
/*
4 4 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.00 1.00
3 4 1.10 1.00 1.00 1.00
4 2 1.10 1.00 1.00 1.00
*/
View Code
1004 : 点的距离:
LCA裸题没什么好说的。这里询问的数量不够明显，所以写的st表比普通还慢。
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e5 + 5;
const int M = 2e3 + 5;
const LL Mod = 100000007;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
int n,st[N << 1][30],dep[N],dfn[N],lg[N << 1],tim = 0,tot = 0;
vector<int> G[N];
void dfs(int u,int fa) {
dfn[u] = ++tot;
dep[u] = dep[fa] + 1;
st[tot][0] = u;
for(auto v : G[u]) {
if(v == fa) continue;
dfs(v,u);
st[++tot][0] = u;
}
}
void init() {
lg[1] = 0;
for(int i = 2;i <= tot;++i) lg[i] = lg[i >> 1] + 1;
for(int j = 1;(1 << j) <= tot;++j) {
for(int i = 1;i + (1 << j) - 1 <= tot;++i) {
if(dep[st[i][j - 1]] <= dep[st[i + (1 << j - 1)][j - 1]]) st[i][j] = st[i][j - 1];
else st[i][j] = st[i + (1 << j - 1)][j - 1];
}
}
}
int LCA(int x,int y) {
x = dfn[x],y = dfn[y];
if(x > y) swap(x,y);
int k = lg[y - x + 1];
if(dep[st[x][k]] < dep[st[y - (1 << k) + 1][k]]) return st[x][k];
else return st[y - (1 << k) + 1][k];
}
int query(int x,int y) {
return dep[x] + dep[y] - 2 * dep[LCA(x,y)];
}
int main() {
scanf("%d",&n);
for(int i = 1;i < n;++i) {
int x,y;scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,0);
init();
int q;scanf("%d",&q);
while(q--) {
int x,y;scanf("%d %d",&x,&y);
printf("%d\n",query(x,y));
}
// system("pause");
return 0;
}
View Code