oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1034 本題N超小的，估了一下到$O(N^6)$甚至$O(N^7)$可能都會過，不過該怎麼做這題呢XD 仔細想想我們如果可以快速得到任意兩點的最短距離的話，那就直接枚舉炸掉所有位置，看看哪樣比較短，也就是說答案就是$\min\limits_{\forall k \in V} dis[a][k]+dis[k][b]-2 \times val[k]$(其中v是所有點的集合)(這是先把二維圖轉一維後的寫法)，而任兩點最短路徑的話就直接寫個floyd-warshall就好了XD 不過說直接floyd-warshall很容易，但本題給的是點權，可能沒辦法好好做，所以我直接用了一個小技巧(或許可以不用用拉XD):把a到b的距離設成$2 \times val[b]-val[a]$，最後算a到b時再加回$2 \times val[a]-val[b]$他的值就會是好的了 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define N 20 #define INF 100000 int g[N+5][N+5]; lld sg[3000][3000]; int n; inline int Hash(int,int); int main(){ scanf("%d",&n); for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&g[i][j]); for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int p=0;p<n;p++)for(int q=0;q<n;q++)sg[Hash(i,j)][Hash(p,q)]=INF; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ...

題目連結: http://tioj.infor.org/problems/1212 本題要找最小環，那要怎麼做呢?其實就直接做Floyd-Warshall，然後看哪一組自己到自己最小，大概就這樣吧XD #include <bits/stdc++.h> using namespace std; #define INF 999999 #define N 500 int graph[N + 10][N + 10]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n!=0||m!=0){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) graph[i][j]=INF; for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); graph[a][b]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]); int mm=INF; for(int i=1;i<=n;i++) mm = min(graph[i][i], mm); if(mm==INF) puts("0"); ...

題目連結: http://tioj.infor.org/problems/1096 本題要找最小環，那要怎麼做呢?其實就直接做Floyd-Warshall，然後看哪一組自己到自己最小，大概就這樣吧XD #include <stdio.h> #define INF 9999999 int graph[101][101]; int main(){ int n; scanf("%d",&n); while(n!=0){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&graph[i][j]); if(graph[i][j]==0)graph[i][j]=INF; } } for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(graph[i][k]+graph[k][j] < graph[i][j]) graph[i][j] =graph[i][k]+graph[k][j]; int min=INF; for(int i=0;i<n;i++) if(graph[i][i]<min) min=graph[i][i]; if(min==INF) puts("-1"); else printf("%d\n...