|
|
这一题仍然是最短路径，一次AC！好高兴啊。题目是单纯的最短路径的小变形，只要从妈妈说的第二个路口开始找最短路径开始就可以了。
 #include <stdio.h>
#define DEBUG 1
const int N=1111 ;
const int Max=0xfffffff ;
int n, sum, map[N][N], dis[N], used[N], mo[30002] ;
void Dijstra( )
   {
 int i, j, index, min ;
  for( i=1; i<=n; ++i ){
//从第二个路口开始找最短路径，因为，第一个
//路口是必须走的，因为妈妈看着我呢！
dis[i] = map[mo[2]][i] ;
used[i] = 0 ;
 }
used[1] = 1 ;
used[mo[2]] = 1 ;
for( i=1; i<=n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
for( j=1; j<=n; ++j )
if( !used[j] && dis[j] > dis[index]+map[index][j] )
dis[j] = dis[index]+map[index][j] ;
}
//计算差值
printf("Y %d\n", sum-dis[n] ) ;
 }
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
#endif
int i, j, k, r, di, flag, x, y, sets, mother ;
scanf("%d", &sets ) ;
for( k=1; k<=sets; ++k ){
printf("TEST %d ", k ) ;
scanf("%d%d", &n, &r ) ;
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j )
map[i][j] = Max ;
map[i][i] = 0 ;
}
for( i=1; i<=r; ++i ){
scanf("%d%d%d", &x, &y, &di ) ;
map[x][y] = map[y][x] = di ;
}
scanf("%d", &mother ) ;
for( i=1; i<=mother; ++i )
scanf("%d", &mo[i] ) ;
sum = flag = 0 ;
//妈妈说第一条路必须走，因为她说她在看着我
//但是最后还是要减掉的，所以要走，但是不加上。
for( i=2; i<mother; ++i ){
//如果没路，就输出 N ！妈妈和我开玩笑呢！
// 继续下一次读入信息
if( map[mo[i]][mo[i+1]] == Max ){
printf("N\n") ;
flag = 1 ;
break ;
}
//按照妈妈说的路线走，看看要走多远
sum += map[mo[i]][mo[i+1]] ;
}
if( !flag )
Dijstra( ) ;
}
return 0 ;
}
题目就是给出一个笛卡尔坐标系，然后给出一些点，问题就是要求最小生成树。我以前没有做过这样的，因为这里，一个点到另一个点的距离没有给出。难道要把一个点到所有的点的距离都求出来？那样的话时间复杂度就太高了吧？ 我发现我现在还是太贪求速度，我确实是想到了这里，但是我没有去做，去写，而是去找别人的代码，先看看别人是怎么写的，然后我再写。其实，他们和我的算法思想是一样的。我以后要尽力改正这一个不好的习惯。这样非常不利于我学习算法。加油！
#include <stdio.h>
#include <math.h>
#define DEBUG 1
const double Max = 0x7fffffff ;
const int N = 111 ;
int n, used[N], closest[N] ;
double map[N][N], pos[N][2], dis[N] ;
double Distance( double *a, double *b )
{
return sqrt( (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]) ) ;
}
double Prim( )
{
int i, j, index ;
double min, len ;
for( i=1; i<=n; ++i ){
used[i] = 0 ;
dis[i] = map[1][i] ;
}
used[1] = 1 ;
len = 0 ;
for( i=1; i<n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
len += dis[index] ;
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[j][index] )
dis[j] = map[j][index] ;
}
}
return len ;
}
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
#endif
int i, j ;
while( EOF != scanf("%d", &n ) ){
for( i=1; i<=n; ++i )
for( j=1; j<=n; ++j )
map[i][j] = Max ;
for( i=1; i<=n; ++i )
scanf("%lf%lf", &pos[i][0], &pos[i][1] ) ;
for( i=1; i<=n; ++i ){
for( j=i+1; j<=n; ++j ){
map[i][j] = map[j][i] = Distance( pos[i], pos[j] ) ;
}
}
printf("%.2lf\n", Prim( ) ) ;
}
return 0 ;
}
虽然这一题已经写过了，但是我觉得这里有问题。因为题目中有这样的一句话： We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected. 这样一来，如果是A-B-C-D，我们能说A和D是相通的吗？我觉得不能，但是参考别人的代码时，他们都没有考虑这一中情况，我也写了一个没有考虑的。竟然过了！不知道为什么。我主要是在练习算法，难道是我理解错了？
#include <stdio.h>
#define DEBUG 1
const int Max = 0x7fffffff ;
const int N = 111 ;
int n, dis[N], used[N], closest[N], map[N][N] ;
int Prim( )
{
int i, j, index, min, len ;
for( i=1; i<=n; ++i ){
used[i] = 0 ;
dis[i] = map[1][i] ;
}
used[1] = 1 ;
len = 0 ;
for( i=1; i<n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
len += dis[index] ;
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[j][index] )
dis[j] = map[j][index] ;
}
}
return len ;
}
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
#endif
int i, j, x, y, comp ;
while( EOF != scanf("%d", &n ) && n ){
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
scanf("%d", &map[i][j] ) ;
map[j][i] = map[i][j] ;
}
}
scanf("%d", &comp ) ;
for( i=1; i<=comp; ++i ){
scanf("%d%d", &x, &y ) ;
map[x][y] = map[y][x] = 0 ;
}
printf("%d\n", Prim( ) ) ;
}
return 0 ;
}
没什么好说的，还是最小生成树，和上一题一样，没有任何变化。我现在只会prim算法，所以就只用prim写。
#include <stdio.h>
#define DEBUG 1
const int N=101 ;
const int Max = 0x7fffffff ;
int n, map[N][N], dis[N], used[N], closest[N] ;
int Prim( )
{
int i, j, index, min, len ;
len = 0 ;
for( i=1; i<=n; ++i ){
dis[i] = map[1][i] ;
used[i] = 0 ;
closest[i] = 1 ;
}
used[1] = 1 ;
for( i=1; i<n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
min = dis[j] ;
index = j ;
}
}
used[index] = 1 ;
len += dis[index] ;
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[index][j] ){
closest[j] = index ;
dis[j] = map[index][j] ;
}
}
}
return len ;
}
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
int i, j, x, y, weight, hangshu ;
while( scanf("%d", &n) && n ){
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
map[i][j] = Max ;
}
}
hangshu = n*(n-1)/2 ;
for( i=1; i<=hangshu; ++i ){
scanf("%d%d%d", &x, &y, &weight ) ;
map[x][y] = map[y][x] = weight ;
}
printf("%d\n", Prim( ) ) ;
}
return 0 ;
}
这是我做的第一个最小生成树的题目。算法思想就是从任意一个点出发，标记为已找到的。然后找到所有与已找到的点相连的边中，权值最小的边。把边的另一个顶点标记为已找到的。然后更新所有与这个刚找到的顶点相邻的顶点的信息。重复这个步骤，直到找到了n-1个顶点。那就组成了一棵最小生成树，就是题目结束了。
#include <stdio.h>
#define DEBUG 1
const int Max = 0x7fffffff ;
const int N = 30 ;
int n, map[N][N], dis[N], used[N] ;
int Prim( )
{
int i, j, index, len, min ;
len = 0 ;
for( i=1; i<=n; ++i ){
// 出发点定义为 1
dis[i] = map[1][i] ;
used[i] = 0 ;
}
// used[]数组作为标志 ，表示已经被标记过的点
used[1] = 1 ;
for( i=1; i<n; ++i ){
min = Max ;
//找到所有与已标记过的点相连的边中，权值最小的边
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
len += dis[index] ;
//更新所有与已找到的点相连的边的信息
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[index][j] )
dis[j] = map[index][j] ;
}
}
return len ;
}
int main()
{
//输入输出的重定向
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
int i, j, d, geshu, weight ;
char ch, to ;
while( scanf("%d", &n) && n ){
//初始化数据
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
map[i][j] = Max ;
}
}
//读入数据
for( i=1; i<n; ++i ){
//吃掉空格，不然机会造成读入数据错误
getchar() ;
scanf("%c %d", &ch, &geshu ) ;
for( j=1; j<=geshu; ++j ){
scanf(" %c %d", &to, &weight ) ;
// -64 是为了把第一个点，也就是A点，当成第一个点
// 因为A的ASCII是65 ，所以65-64 就是 1
// 建立的是无向图
map[i][to-64] = map[to-64][i] = weight ;
}
}
printf("%d\n", Prim( ) ) ;
}
return 0 ;
}
又是一道典型的最短路径的题目，当然也可以用搜索，我现在在学习最短路径，所以就用Dijsktra来做的，一开始时WA了好几次，是因为这一题是应该抽象出来一个有向图，而我却是用了无向图，所以一直WA。最后改了一下，然后就过了。
#include <stdio.h>
#define DEBUG 1
const int N=300 ;
const int Max = 10000000 ;
int n, map[N][N], used[N], dis[N] ;
void Dijkstra( int a, int b )
{
int i, j, index, min ;
for( i=1; i<=n; ++i ){
dis[i] = map[a][i] ;
used[i] = 0 ;
}
used[a] = 1 ;
for( i=1; i<=n; ++i ){
index = a ;
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min > dis[j] ){
min = dis[j] ;
index = j ;
}
}
used[index] = 1 ;
for( j=1; j<=n; ++j ){
if( dis[j] > dis[index]+map[index][j] )
dis[j] = dis[index]+map[index][j] ;
}
}
if( dis[b] == Max ){
//printf("%d\n", dis[b] ) ;
printf("-1\n") ;
}
else
printf("%d\n", dis[b] ) ;
}
int main( )
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
int i, j, a, b, temp ;
while( scanf("%d", &n) && n ){
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j )
map[i][j] = Max ;
map[i][i] = 0 ;
}
scanf("%d%d", &a, &b ) ;
for( i=1; i<=n; ++i ){
scanf("%d", &temp ) ;
if( i - temp > 0 )
map[i][i-temp] = 1 ;
if( i + temp <= n )
map[i][i+temp] = 1 ;
}
Dijkstra( a, b ) ;
}
return 0 ;
}
#include <stdio.h>
#define DEBUG 1
const int N=300 ;
const int Max = 10000000 ;
int n, map[N][N], used[N], dis[N] ;
void Dijkstra( int a, int b )
{
int i, j, index, min ;
for( i=1; i<=n; ++i ){
dis[i] = map[a][i] ;
used[i] = 0 ;
}
used[a] = 1 ;
for( i=1; i<=n; ++i ){
index = a ;
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min > dis[j] ){
min = dis[j] ;
index = j ;
}
}
used[index] = 1 ;
for( j=1; j<=n; ++j ){
if( dis[j] > dis[index]+map[index][j] )
dis[j] = dis[index]+map[index][j] ;
}
}
if( dis[b] == Max ){
//printf("%d\n", dis[b] ) ;
printf("-1\n") ;
}
else
printf("%d\n", dis[b] ) ;
}
int main( )
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
int i, j, a, b, temp ;
while( scanf("%d", &n) && n ){
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j )
map[i][j] = Max ;
map[i][i] = 0 ;
}
scanf("%d%d", &a, &b ) ;
for( i=1; i<=n; ++i ){
scanf("%d", &temp ) ;
if( i - temp > 0 )
map[i][i-temp] = 1 ;
if( i + temp <= n )
map[i][i+temp] = 1 ;
}
Dijkstra( a, b ) ;
}
return 0 ;
}
这一星期我在学习单源最短路径，今天是这一星期的最后一天。我半写半参考的写出了这一题，要用到DFS+Dijsktra。
题目是让求一个点到另一个点的“前进的”(就是越走离家越近，这是一个难点，不然就做不出来)路径的条数。算法思想是：先求出家到每一个顶点的最短路径，然后用深搜求出从公司到家的路径的条数。
#include <stdio.h>
#include <memory.h>
#define debug 1
#define N 1010
//要注意不要把Max定义的太大，不然会在做加法时溢出，
// 当然，要是不做加法，就没事了，可以定义为2147483647
//也可以用 __int64 ，但是那样的效率比较低
#define Max 10000000
int n ;
int map[N][N], dis[N], used[N], num[N] ;
void Input( )
{
int i, j, x, m, y, distance ;
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
map[i][j] = Max ;
}
//自己到自己的最短路径是0
map[i][i] = 0 ;
}
scanf("%d", &m ) ;
for( i=0; i<m; ++i ){
scanf("%d%d%d", &x, &y, &distance ) ;
//用无向图来存储数据
map[x][y] = distance ;
map[y][x] = distance ;
}
}
void Dijstra( int v )
{
int i, j, min, index ;
for( i=1; i<=n; ++i ){
//求家到各个顶点的初始路径的距离，如果没有路径，就是Max
dis[i] = map[v][i] ;
//用来标记是否已经求过
used[i] = 0 ;
}
// 从家里出发，家已经走过，标记为1，下同
used[v] = 1 ;
for( i=1; i<=n; ++i ){
min = Max ;
index = v ;
//找到与每一个已标记过的顶点之间距离最小的顶点
for( j=1; j<=n; ++j ){
if( !used[j] && min > dis[j] ){
index = j ;
min = dis[j] ;
}
}
//已经找到，标记
used[index] = 1 ;
//更新与刚找到的顶点相邻的顶点的最短路径
for( j=1; j<=n; ++j ){
if( dis[j] > dis[index] + map[index][j] )
dis[j] = dis[index] + map[index][j] ;
}
}
}
int DFS( int nod )
{
int i, count ;
//如果已到家，就返回1，表示找到了一条路
if( nod == 2 )
return 1 ;
//如果这一点已经求过，就返回这一点到家的路径的条数
if( num[nod] > 0 )
return num[nod] ;
count = 0 ;
//对每一个顶点进行判断，并求路径的条数
for( i=1; i<=n; ++i ){
if( map[i][nod]<Max && dis[i]<dis[nod] )
count += DFS( i ) ;
}
//标记路径的条数，并返回值
num[nod] = count ;
return count ;
}
int main()
{
// 输入输出的重定向，便于调试，在提交时要把debug改成0
#if debug
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
while( scanf("%d",&n) && n ){
//读入数据
Input( ) ;
//调用Dijsktra 求家到每一个节点的最短路径
Dijstra( 2 ) ;
// 数据初始化
memset( num, 0, sizeof(num) ) ;
// 用深搜求的路径的条数
printf("%d\n", DFS( 1 ) ) ;
}
return 0 ;
}
#include <iostream>
using namespace std;
const int lmax=10000;
//c1是用来存放展开式的系数的，而c2则是用来计算时保存的，
//他是用下标来控制每一项的位置，比如 c2[3] 就是 x^3 的系数。
//用c1保存，然后在计算时用c2来保存变化的值。
int c1[lmax+1],c2[lmax+1];
int main()
{
int n, i, j, k ;
// 计算的方法还是模拟手动运算，一个括号一个括号的计算，
// 从前往后
while ( cin>>n ){
//对于 1+x+x^2+x^3+ 他们所有的系数都是 1
// 而 c2全部被初始化为0是因为以后要用到 c2[i] += x ;
for ( i=0; i<=n; i++ ){
c1[i]=1;
c2[i]=0;
}
//第一层循环是一共有 n 个小括号，而刚才已经算过一个了
//所以是从2 到 n
for (i=2; i<=n; i++){
// 第二层循环是把每一个小括号里面的每一项，都要与前一个
//小括号里面的每一项计算。
for ( j=0; j<=n; j++ )
//第三层小括号是要控制每一项里面 X 增加的比例
// 这就是为什么要用 k+= i ;
for ( k=0; k+j<=n; k+=i ){
// 合并同类项，他们的系数要加在一起，所以是加法，呵呵。
// 刚开始看的时候就卡在这里了。
c2[j+k] += c1[j];
}
// 刷新一下数据，继续下一次计算，就是下一个括号里面的每一项。
for ( j=0; j<=n; j++ ){
c1[j] = c2[j] ;
c2[j] = 0 ;
}
}
cout<<c1[n]<<endl;
}
return 0;
}
|