ACM第六次比赛题目及标准程序（动态规划）

#include#includeint pre[1080];
//并查集模板题 
int Find(int x)//找老板 
{
int r=x;
while(r!=pre[r])
r=pre[r];
return r;
}
void merge(int x,int y)//联合
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
pre[fy]=fx;
}
int main()
{
int casenum;
scanf("%d",&casenum);
while(casenum--)
{
int N,M,a,b,i,j,ans;
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++)//初始化i的父结点为其本身 
pre[i]=i;
for(i=1;i<=M;i++)//吸收并整理
{
scanf("%d%d",&a,&b);
merge(a,b);
}
for(ans=0,i=1;i<=N;i++)
if(pre[i]==i)
ans++;//判断有几个独立块
printf("%d\n",ans);
}
return 0;
}

问题E:爱旅游的小明

#include#include#includeusing namespace std;
const int INF=0x3f3f3f3f;
const int N=210;
int n,m,cnt;
int dis[N];
struct node{
int u,v,w;
}edge[1010*2];
void addedge(int u,int v,int w)
{
edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w;
cnt++;
edge[cnt].u=v; edge[cnt].v=u; edge[cnt].w=w;
cnt++;
}
int Bellman_Ford(int src,int des)
{
int i,k;
for(i=0;i到某边终点的距离加上这条边的长度 
if(dis[edge[i].u]!=INF && dis[edge[i].v]>dis[edge[i].u]+edge[i].w)  
dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
return dis[des]==INF?-1:dis[des];
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
cnt=0;
int u,v,w;
for(int i=0;i#include #include using namespace std; //4种解法 比较简单的是Dijkstra和Floyd。另外两种相对更难理解 const int INF=0x3f3f3f3f; const int N=210; int n,m,s,t; int map[N][N],dis[N],vis[N]; void Dijkstra(int src) { int i,j,k,tmp; for(i=0;i dis[j]) k=j,tmp=dis[j]; if(tmp==INF) break; vis[k]=1; for(j=0;j dis[k]+map[k][j]) dis[j]=dis[k]+map[k][j]; } } int main() { while(~scanf("%d%d",&n,&m)) { int u,v,w; for(int i=0;i w) map[u][v]=map[v][u]=w; } scanf("%d%d",&s,&t); Dijkstra(s);//计算从点s到其他所有点的距离 if(dis[t]==INF) printf("-1\n"); else printf("%d\n",dis[t]); } return 0; }#include #include #include #include using namespace std; const int INF=0x3f3f3f3f; const int N=210; int n,m,i,j,k,map[N][N]; //Floyd算法可能是最容易理解的，但是有利有弊。 //遇到稍微严格数据，超时的可能性非常大。毕竟3个for循环嵌套 void Floyd() { for(k=0;k map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; } int main() { while(~scanf("%d%d",&n,&m)) { for(i=0;i w) map[u][v]=map[v][u]=w; } int s,t; scanf("%d%d",&s,&t); Floyd(); if(map[s][t]==INF) printf("-1\n"); else printf("%d\n",map[s][t]); } return 0; }#include #include #include using namespace std; #define N 205 #define INF 99999999 int n,m,map[N][N]; int visited[N],dis[N]; int SPFA(int src,int des) { int i; for(i=0;i myqueue; while(!myqueue.empty()) myqueue.pop(); dis[src]=0; visited[src]=1; myqueue.push(src); int tmp; while(!myqueue.empty()) { tmp=myqueue.front(); myqueue.pop(); visited[tmp]=0; for(i=0;i dis[tmp]+map[tmp][i]) { dis[i]=dis[tmp]+map[tmp][i]; if(!visited[i]) { visited[i]=1; myqueue.push(i); } } } } return dis[des]; } int main() { int u,v,cost; while(scanf("%d%d",&n,&m)!=EOF) { int i,j; for(i=0;i