路径只能由小序号到大序号..（起点可以视为最小的序号和最大的序号） 问怎么走 happy值最大..
DFS
N=100 且只能小序号到大序号 显然dfs可以过..
但是存路径的时候sb了.....应该在更新答案时拿一个ans_dis数组去全部存一遍路径...
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
const int maxn=105;
const int inf=-0x3f3f3f3f;
int w[maxn];
int dis[maxn];
struct edge
{
int to;
edge *next;
}E[maxn*maxn],*EE;
struct node
{
edge *frist;
}Graph[maxn];
int N,M;
int pre[maxn];
void Link(int u,int v)
{
EE->to=v;EE->next=Graph[u].frist;Graph[u].frist=EE++;
// EE->to=u;EE->next=Graph[v].frist;Graph[v].frist=EE++;
}
void input()
{
cin>>N;
memset(Graph,0,sizeof(Graph));
memset(pre,0,sizeof(pre));
memset(dis,0,sizeof(dis));
EE=E;
for(int i=1;i<=N;i++)
{
scanf("%d",&w[i]);
}
cin>>M;
int a,b;
for(int i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
if(b==N+1) b=1;
if(a==N+1) a=1;
Link(a,b);
}
}
int ans=-1;
int dfs(int P,int n,int ok,int W)
{
pre[n]=P;
if(ok==1&&n==1)
{
if(W>ans)
{
int p=pre[n];
dis[n]=pre[n];
while(p!=1)
{dis[p]=pre[p];p=pre[p];}
ans=W;
}
return 0;
}
else
{
for(edge *p=Graph[n].frist;p;p=p->next)
{
if(p->to>n||p->to==1){dfs(n,p->to,1,W+w[n]);}
}
}
}
void output(int n,int ok)
{
if(n==1&&ok==1)
{
printf("%d",n);
}
else {
output(dis[n],1);
printf("->%d",n);
}
}
int CASE=0;
int T;
void solve()
{
ans=inf;
dfs(0,1,0,0);
printf("%d
",ans);
printf("circuit : ");
output(1,0);
printf("
");
if(T!=0) printf("
");
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int main()
{
// init();
cin>>T;
while(T--)
{
printf("CASE %d#
",++CASE);
printf("points : ");
input();
solve();
}
return 0;
}
最短路
Floyd
利用floyd..在循环的时候修改一下循环次数即可
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
const int maxn=105;
const int inf=-0x3f3f3f3f;
int T;
int N,M;
int w[maxn];
int MAP[maxn][maxn];
int F[maxn][maxn];
int dis[maxn][maxn];
void input()
{
memset(MAP,0,sizeof(MAP));
memset(dis,0,sizeof(dis));
int a,b;
cin>>N;
for(int i=1;i<=N;i++)
{
scanf("%d",&w[i]);
w[i]=-w[i];
}
w[N+1]=0;
cin>>M;
for(int i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
MAP[a][b]=1;
}
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
{
F[i][j]=-inf;
if(MAP[i][j]==1)
F[i][j]=0;
}
}
void floyed()
{
for(int i=1;i<=N+1;i++)
for(int j=1;j<=N+1;j++)
dis[i][j]=j;
for(int k=1;k<=N+1;k++)
for(int i=1;i<k;i++)
for(int j=k+1;j<=N+1;j++)
{
if(F[i][k]+F[k][j]+w[k]<F[i][j])
{
F[i][j]=F[i][k]+F[k][j]+w[k];
dis[i][j]=dis[i][k];
}
}
printf("points : %d
",-F[1][N+1]);
printf("circuit : ");
for(int p=1;1;p=dis[p][N+1])
{
if(p==N+1){printf("1");break;}
else{
printf("%d->",p);
}
}
printf("
");
if(T!=0) printf("
");
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int main()
{
int CASE=0;
// init();
cin>>T;
while(T--)
{
printf("CASE %d#
",++CASE);
input();
floyed();
}
}