博文
Zju 1203 Swordfish(2006-08-01 23:01:00)
摘要：
1991483
2006-08-01 22:46:34
Accepted
1203
C++
00:00.01
480K
St.Crux
O(n^3)。用邻接矩阵做的。什么？prim是什么......求最小生成树。不过我总觉得这个算法有待提高......
另：double必须要用%lf来读入
#include <cstdio>#include <string>#include <cmath>
double a[100][100], sum, p[100][2]; int b[100], n;
void prim(){ int i, k, j, sp, ep; sum = 0; for(i = 1; i < n; i ++) { double min = 30000; for(k = 0; k < n; k ++) // 起点边 { if(!b[k]) continue; for(j = 0; j < n; j ++) // 终点边 { if(b[j]) continue; if(a[k][j] < min) { min = a[k][j]; sp = k, ep = j; } } } sum += min; b[ep] = 1; }}
void init(){ int i, k; memset(b, 0, sizeof(b)); b[0] = 1; for(i = 0; i < n; i ++)&nb......
ZOJ 1221 Risk(2006-07-27 00:10:00)
摘要：/* source: zju 1221 *//* algo: floyd *//* author: St.Crux */
#include <cstdio>
int m[20][20];
int main(){ //freopen("in.txt", "r", stdin); int i, k, j, n, a, t = 0; while(scanf("%d", &a) != EOF) { for(i = 0; i < 20; i ++) { for(k = 0; k < 20; k ++) { m[i][k] = ((i == k) ? 0 : 100); } } for(k = 0; k < a; k ++) { scanf("%d", &j); m[0][j - 1] = 1; m[j - 1][0] = 1; } for(i = 1; i < 19; i ++) { scanf("%d", &a); for(k = 0; k < a; k ++) { scanf("%d", &j); m[i][j - 1] = 1; m[j - 1][i] = 1; } } &n......