175 条题解
-
-1
-
-1
#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 15, M = 2e5 + 10; vector<int> edge[N]; int h[N], e[M], ne[M], idx, p[N]; int in[N]; int n, m; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; in[b]++; } int dfn[N], low[N], tot = 0; stack<int> stk; bool st[N]; int sz[N], scc[N], color; void tarjan(int u) { dfn[u] = low[u] = ++tot; stk.push(u); st[u] = true; for (int v : edge[u]) { if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if (st[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { ++color; while (stk.top() != u) { scc[stk.top()] = color; st[stk.top()] = false; stk.pop(); } scc[stk.top()] = color; st[stk.top()] = false; stk.pop(); } } queue<int> q; int dp[N]; void topsort() { for (int i = 1; i <= color; i++) { dp[i] = sz[i]; if (in[i] == 0) q.push(i); } while (q.size()) { int u = q.front(); q.pop(); for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; dp[v] = max(dp[v], dp[u] + sz[v]); in[v]--; if (in[v] == 0) q.push(v); } } int ans = 0; for (int i = 1; i <= color; i++) ans = max(ans, dp[i]); printf("%d\n", ans); } int main() { memset(h, -1, sizeof h); n = 2, m = 1; for (int i = 1; i <= n; i++) scanf("%d", &p[i]); while (m--) { int a = 1, b = 2; edge[a].push_back(b); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; i++) { sz[scc[i]] += p[i]; for (int j : edge[i]) if (scc[i] != scc[j]) add(scc[i], scc[j]); } topsort(); return 0; }
转自AcWing@Conan15
-
-1
A+B问题居然没有高精度题解,发一篇吧!
#include <bits/stdc++.h> using namespace std; const int maxn=250; char sa[maxn],sb[maxn];//定义两个字符串 int a[maxn],b[maxn],c[maxn];//a,b位数字,c进位 int main() { scanf ("%d",sa); scanf ("%d",sb); memset (c,0,sizeof(c));//初始化赋值为0 int la=strlen (sa);//取字符串长度 int lb=strlen (sb); for (int i=0;i<la;i++) a[la-i-1]=sa[i]-'0'; for (int i=0;i<lb;i++) b[lb-i-1]=sb[i]-'0';//将两个字符串类型的数转换成整数 int lc=la>lb?la:lb;//三目运算符,取两个数字中数位最长的数字的数位 for (int i=0;i<lc;i++) { c[i] += a[i]+b[i];//加法运算 if (c[i]>=10) { c[i+1]=a[i]/10; c[i]=c[i]%10;//进位 } } if (c[lc]>0) lc++; int cnt=lc-1; while (c[cnt]==0) cnt--; for (int i=cnt;i>=0;i--) printf ("%d",c[i]); return 0; }
信息
- ID
- 56
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 1
- 标签
- 递交数
- 10304
- 已通过
- 4651
- 上传者