Hướng dẫn giải của VM 10 Bài 01 - Điều kiện thời tiết
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxn=110; var n,m,last,sm,dem,re:longint; a,e:array[1..maxn,1..maxn] of boolean; b:array[1..maxn,1..maxn] of longint; free:array[1..maxn] of boolean; d,sl,low,num,st,dau,q:array[1..maxn] of longint; procedure rf; var i,x,y:longint; begin assign(input,fi); reset(input); readln(n); readln(m); for i:=1 to m do begin readln(x,y); a[x,y]:=true; a[y,x]:=true; end; close(input); end; function pop:longint; begin pop:=st[last]; dec(last); end; procedure push(i:longint); begin inc(last); st[last]:=i; end; function min(x,y:longint):longint; begin if x<y then min:=x else min:=y; end; procedure visit(x,y:longint); var i:longint; begin inc(dem); num[x]:=dem; low[x]:=dem; push(x); for i:=1 to n do if free[i] and a[x,i] and (i<>y) then begin if num[i]>0 then low[x]:=min(num[i],low[x]) else begin visit(i,x); low[x]:=min(low[x],low[i]); end; end; if num[x]=low[x] then begin inc(sm); repeat i:=pop; free[i]:=false; d[i]:=sm; until i=x; d[x]:=sm; end; end; procedure pr; var i,j,k,l,high:longint; begin last:=0; sm:=0; dem:=0; for i:=1 to n do free[i]:=true; for i:=1 to n do if free[i] then visit(i,0); for i:=1 to n do begin inc(sl[d[i]]); b[d[i],sl[d[i]]]:=i; end; re:=0; for i:=1 to n-1 do for j:=i+1 to n do if a[i,j] then begin e[d[i],d[j]]:=true; e[d[j],d[i]]:=true; end; for i:=1 to n-1 do for j:=i+1 to n do begin fillchar(dau,sizeof(dau),0); dau[d[i]]:=1; high:=1; q[1]:=d[i]; l:=1; repeat for k:=1 to sm do if (dau[k]=0) and e[q[l],k] then begin inc(high); q[high]:=k; dau[k]:=dau[q[l]]+1; end; inc(l); until (l>high) or (dau[d[j]]>0); if dau[d[j]]>0 then re:=re+dau[d[j]]-1; end; end; procedure wf; begin assign(output,fo); rewrite(output); writeln(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; typedef long long LL; #define sz(a) (int((a).size())) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 105 int n, m; vvi g; vii e; int qu[N], lq, hq; bool vst[N]; int bfs(int U, int V) { lq = 0; hq = 1; qu[0] = 0; memset(vst, 0, sizeof vst); vst[0] = 1; int res = 0; while(lq != hq) { int u = qu[lq++]; ++res; tr(g[u], it) { if(!vst[*it] && !(u == U && V == *it || U == *it && V == u)) { vst[*it] = 1; qu[hq++] = *it; } } } return res; } int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); #endif scanf("%d%d",&n,&m); g.resize(n); rep(i,m) { int u, v; scanf("%d%d",&u,&v); g[--u].pb(--v); g[v].pb(u); e.pb(ii(u,v)); } LL res = 0; tr(e, it) { LL t = (LL) bfs(it->fi, it->se); res += t * (n-t); } printf("%lld\n", res); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int N = 1000; int par[N]; int size[N]; vector<int> a[N]; int low[N], num[N]; int n, m; int Time; void dfs(int u) { num[u] = ++Time; low[u] = N; size[u] = 1; for (int v : a[u]) if (v != par[u]) { if (num[v] == 0) { par[v] = u; dfs(v); low[u] = min(low[u], low[v]); size[u] += size[v]; } else { low[u] = min(low[u], num[v]); } } } int main() { cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } dfs(1); int ans = 0; for (int v = 2; v <= n; ++v) { if (low[v] >= num[v]) ans += size[v] * (n - size[v]); } cout << ans << endl; return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #include <vector> #define FOR(i,a,b) for(int i=a; i<=b; i++) #define FORD(i,a,b) for(int i=a; i>=b; i--) #define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++) #define V vector<int> #define _ [111] using namespace std; int n,m,res=0,now=0; int low _, num _, father _, weight _; V ke _; void inp() { scanf("%d %d",&n,&m); FOR(i,1,m) { int u,v; scanf("%d %d",&u,&v); ke[u].push_back(v); ke[v].push_back(u); } } void dfs(int u) { now++; num[u]=now; low[u]=now; weight[u]=1; FORV(v,ke[u]) { if (*v==father[u]) continue; if (!father[*v]) { father[*v]=u; dfs(*v); weight[u]+=weight[*v]; low[u]=min(low[u],low[*v]); } else low[u]=min(low[u],num[*v]); } } void solve() { father[1]=1; dfs(1); FOR(v,2,n) { int u=father[v]; if (low[v]>num[u]) { // cout<<u<<" "<<v<<" "<<weight[v]<<endl; res+=weight[v]*(n-weight[v]); } } cout<<res; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); inp(); solve(); return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = { -1, 0, +1, 0}; const int dc[] = { 0, +1, 0, -1}; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const int mod = (ll) (1e9 + eps); #define ok puts("ok") #define maxn 105 #define maxe 20005 int last[maxn], adj[maxe], next[maxe], E = 0, flag[maxn], run, f[maxn], vt[maxn]; int n, m, res; void add(int u, int v){ adj[E] = v; next[E] = last[u]; last[u] = E++; adj[E] = u; next[E] = last[v]; last[v] = E++; } int cal(int par, int u){ if(flag[u]) return 0; flag[u] = 1; int ret = 1; for(int e = last[u]; e != -1; e = next[e]){ int v = adj[e]; if(v == par) continue; ret += cal(u, v); } return ret; } void go(int par, int u){ f[u] = run; vt[u] = run++; for(int e = last[u]; e != -1; e = next[e]){ int v = adj[e]; if(v == par) continue; if(vt[v] > -1) f[u] = min(f[u], vt[v]); else{ go(u, v); f[u] = min(f[u], f[v]); if(f[v] > vt[u]){ ms(flag, 0); int num = cal(u, v); res += num * (n - num); } } } } int main(){ // freopen("in.txt", "r", stdin); cin >> n >> m; int u, v; ms(last, -1); Rep(mi, m){ scanf("%d %d", &u, &v); add(u, v); } ms(f, -1); ms(vt, -1); res = 0; go(0, 1); run = 0; cout << res; return 0; }
Code mẫu của ll931110
//#pragma comment(linker, "/STACK:16777216") #include <algorithm> #include <bitset> #include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> #include <utility> using namespace std; int n,m; vector<int> adj[105]; int low[105],num[105],sz[105],pre[105],cnt = 0; long long ret = 0; void DFS(int u) { num[u] = low[u] = ++cnt; sz[u] = 1; for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (pre[u] == v) continue; if (!num[v]) { pre[v] = u; DFS(v); sz[u] += sz[v]; if (low[v] > num[u]) ret += 1LL * sz[v] * (n - sz[v]); low[u] = min(low[u],low[v]); } else if (pre[v] != u) low[u] = min(low[u],low[v]); } } int main() { // freopen("weather.in","r",stdin); // freopen("weather.ou","w",stdout); scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int x,y; scanf("%d %d", &x, &y); if (x == y) continue; adj[x].push_back(y); adj[y].push_back(x); } memset(pre,-1,sizeof(pre)); DFS(1); cout << ret << endl; }
Code mẫu của skyvn97
#include<cstdio> #include<vector> #define MAXV 111 #define MAXE 5050 using namespace std; struct edge { int u,v; }; vector<int> g[MAXV]; bool a[MAXV][MAXV]; edge e[MAXE]; int m,n,c,r; int num[MAXV]; int low[MAXV]; int up[MAXV]; void loadgraph(void) { int i,j; scanf("%d",&n); scanf("%d",&m); for (i=1;i<=n;i=i+1) for (j=1;j<=n;j=j+1) a[i][j]=false; for (i=1;i<=m;i=i+1) { scanf("%d",&e[i].u); scanf("%d",&e[i].v); g[e[i].u].push_back(e[i].v); g[e[i].v].push_back(e[i].u); a[e[i].u][e[i].v]=true; a[e[i].v][e[i].u]=true; } for (i=1;i<=n;i=i+1) num[i]=0; c=0; } int find(int x) { if (up[x]<0) return (x); up[x]=find(up[x]); return (up[x]); } void join(int a,int b) { int x=find(a); int y=find(b); if (x==y) return; up[x]=up[x]+up[y]; up[y]=x; } int bridge(int u,int v) { int i; for (i=1;i<=n;i=i+1) up[i]=-1; for (i=1;i<=m;i=i+1) { if ((e[i].u==u) && (e[i].v==v)) continue; if ((e[i].u==v) && (e[i].v==u)) continue; join(e[i].u,e[i].v); } for (i=1;i<=n;i=i+1) if (up[i]<0) return ((-up[i])*(n+up[i])); } void visit(int u) { int i,v; c=c+1; num[u]=c; low[u]=n+1; for (i=0;i<g[u].size();i=i+1) { v=g[u][i]; if (!a[u][v]) continue; a[v][u]=false; if (num[v]==0) { visit(v); if (low[u]>low[v]) low[u]=low[v]; if (low[v]>num[u]) r=r+bridge(u,v); } else if (low[u]>num[v]) low[u]=num[v]; } } void process(void) { int i; r=0; for (i=1;i<=n;i=i+1) if (num[i]==0) visit(i); printf("%d",r); } int main(void) { loadgraph(); process(); return 0; }
Bình luận