博文
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;
}
}
voi......
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);
&n......