今天决定刷图论了，做到至少比赛的时候图论的题能够写出来。。。
用Dijkstra即可。。
因为这题可以抽象出边上有权值，点上也有权值。。我们可以先忽略点上的权值，用Dijkstra算出1~n的最短路，最后再加上点上的权值，然后求所有点的最小值即可。。否则把点上的权值也带入求最小值，会wa。。。我被wa了N次了。。。
这题有等级制度，故需要枚举区间进行多次最短路。
View Code
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 105
#define MM 100000000
using namespace std;
int g[MAXN][MAXN];
int v[MAXN];
int d[MAXN];
int vis[MAXN];
int rank[MAXN];
int dis(int n,int m,int a,int b)
{
int ans=v[1];
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
d[i]=MM;
d[1]=0;
for(int i=1;i<=n;i++)
{
if(g[1][i]&&rank[i]<=b&&rank[i]>=a)
{
d[i]=g[1][i];
}
}
vis[1]=1;
for(int i=1;i<=n;i++)
{
int minn=MM;
int k=0;
for(int j=1;j<=n;j++)
{
if(d[j]<minn&&!vis[j])
{
minn=d[j];
k=j;
}
}
vis[k]=1;
if(k==0)
break;
// return ans;
// ans=min(ans,d[k]);
for(int j=1;j<=n;j++)
{
if(g[k][j]&&!vis[j]&&rank[j]<=b&&rank[j]>=a&&d[k]+g[k][j]<d[j])
d[j]=d[k]+g[k][j];
}
}
for(int i=1;i<=n;i++)
ans=min(ans,d[i]+v[i]);
return ans;
}
int main(){
int n,m;
while(scanf("%d%d",&m,&n)==2)
{
memset(g,0,sizeof(g));
int k;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&v[i],&rank[i],&k);
for(int j=1;j<=k;j++)
{
int a,b;
scanf("%d%d",&a,&b);
g[i][a]=b;
}
}
int ans=v[1];
for(int i=rank[1]-m;i<=rank[1];i++)//枚举区间
{
ans=min(dis(n,m,i,i+m),ans);
}
printf("%dn",ans);
}
return 0;
}
这题是求所有最短路中的最大值。。用dijkstra即可View Code
#include <cstdio>
#include <cstring>
#include <iostream>
#define MM 1000000000
#define MAXN 105
using namespace std;
int g[MAXN][MAXN];
int d[MAXN],vis[MAXN];
int dis(int s,int n)
{
int ans=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
d[i]=g[1][i];
}
vis[1]=1;
for(int i=1;i<=n;i++)
{
int minc=MM,k=0;
for(int j=1;j<=n;j++)
{
if(d[j]<minc&&!vis[j])
{
minc=d[j];k=j;
}
}
if(k==0)
// return ans;
break;
vis[k]=1;
//ans+=d[k];
ans=max(ans,minc);
for(int j=1;j<=n;j++)
{
if(g[k][j]+d[k]<d[j]&&!vis[j])
d[j]=g[k][j]+d[k];
}
// return ans;
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
char ch[100];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)
g[i][j]=0;
else
g[i][j]=MM;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
scanf("%s",ch);
if(ch[0]=='x')
continue;
int s=0;
int len=strlen(ch);
for(int k=0;k<len;k++)
s=s*10+ch[k]-'0';
// scanf("%d",&g[i][j]);
g[j][i]=g[i][j]=s;
// printf("%d %d %dn",i,j,s);
}
}
printf("%dn",dis(1,n));
}
POJ-2387-Til the Cows Come Home
这题目要注意重边。。。dij算法要考虑重边
啊啊啊，以后做图论题得先把特殊情况都先考虑好啊啊。。View Code
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 1005
#define INF 1000000000
using namespace std;
int g[MAXN][MAXN];
int vis[MAXN],d[MAXN];
int T,N;
int dij(int s,int end)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=N;i++)
if(g[s][i])
d[i]=g[s][i];
else d[i]=INF;
d[s]=0;
for(int i=1;i<=N;i++)
{
int minc=INF,k=0;
for(int j=1;j<=N;j++)
if(d[j]<minc&&!vis[j])
{
minc=d[j];k=j;
}
if(k==0)
break;
vis[k]=1;
if(k==end)
return d[k];
for(int j=1;j<=N;j++)
if(!vis[j]&&d[j]>d[k]+g[k][j]&&g[k][j])
d[j]=d[k]+g[k][j];
}
return d[end];
}
int main()
{
scanf("%d%d",&T,&N);
int a,b,c;
memset(g,0,sizeof(g));
for(int i=1;i<=T;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(g[a][b])
g[a][b]=g[b][a]=min(g[a][b],c);
else
g[a][b]=g[b][a]=c;
}
printf("%dn",dij(N,1));
}
这题还好，挺好做的，只是需要转换一点罢了，用dijView Code
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF 1000000000
#define MAXN 1005
using namespace std;
int g[MAXN][MAXN];
int N,M,X;
int gg[MAXN][MAXN];
int vis[MAXN],d[MAXN];
int ans[MAXN];
void dis(int s,int m[MAXN][MAXN])
{
for(int i=1;i<=N;i++)
if(m[s][i])
d[i]=m[s][i];
else d[i]=INF;
d[s]=0;
memset(vis,0,sizeof(vis));
vis[s]=1;
for(int i=1;i<=N;i++)
{
int minc=INF,k=0;
for(int j=1;j<=N;j++)
{
if(!vis[j]&&d[j]<minc)
{
minc=d[j];k=j;
}
}
if(k==0)
break;
vis[k]=1;
for(int j=1;j<=N;j++)
{
if(!vis[j]&&d[j]>d[k]+m[k][j]&&m[k][j])
d[j]=d[k]+m[k][j];
}
}
for(int i=1;i<=N;i++)
ans[i]+=d[i];
}
int main()
{
int a,b,t;
scanf("%d%d%d",&N,&M,&X);
memset(g,0,sizeof(g));
memset(gg,0,sizeof(gg));
memset(ans,0,sizeof(ans));
for(int i=1;i<=M;i++)
{
scanf("%d%d%d",&a,&b,&t);
g[a][b]=gg[b][a]=t;
}
dis(X,g);
dis(X,gg);
int maxn=0;
for(int i=1;i<=N;i++)
maxn=max(ans[i],maxn);
printf("%dn",maxn);
}
题意：在一个城市里，有n（1~1000000）个运输中心，有m条有向路连接着任意的两个运输中心。ACM组织（位于编号为1的运输中心）要派发p个雇佣员工早上前往这p个运输中心去发传单，晚上再让他们都回到组织中。问所有人所走路程的总和最短是多少？
因为是稀疏图，所以用邻接表，所以用spfa算法。输入的时候存两个图，一个是原图，一个是原图的每条边都反向的图。。这样求两次spfa从一点到其他所有点的距离即可。View Code
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 1000050
#define INF 1000000000
using namespace std;
struct node{
int v,w,next;
}edge1[MAXN];
node edge2[MAXN];
int first1[MAXN],first2[MAXN];
long long d[MAXN];
int q[MAXN],vis[MAXN];
int P,Q;
int e1,e2;
void init(int n)
{
memset(first1,-1,sizeof(first1));
memset(first2,-1,sizeof(first2));
e1=0,e2=0;
}
void add1(int u,int v,int w)
{
edge1[e1].v=v;
edge1[e1].w=w;
edge1[e1].next=first1[u];
first1[u]=e1++;
}
void add2(int u,int v,int w)
{
edge2[e2].v=v;
edge2[e2].w=w;
edge2[e2].next=first2[u];
first2[u]=e2++;
}
long long spfa(int s,node *edge,int *first)
{
long long ans=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=P;i++)
d[i]=INF;
d[s]=0;
int rear=0,front=0;
q[rear++]=s;
while(rear!=front)
{
int u=q[front++];
if(front>P)
front=0;
vis[u]=0;
for(int i=first[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(d[v]>d[u]+edge[i].w)
{
d[v]=d[u]+edge[i].w;
if(!vis[v])
{
vis[v]=1;
q[rear++]=v;
if(rear>P)
rear=0;
}
}
}
}
for(int i=1;i<=P;i++)
ans+=d[i];
return ans;
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
int a,b,c;
scanf("%d%d",&P,&Q);
init(P);
for(int i=1;i<=Q;i++)
{
scanf("%d%d%d",&a,&b,&c);
add1(a,b,c);
add2(b,a,c);
}
long long ans=0;
ans+=spfa(1,edge1,first1);
ans+=spfa(1,edge2,first2);
cout<<ans<<endl;
}
}
题意：Bob现在有的钱数为coin，他想从城市1到城市n，给出m条连接两个城市的有向边，并且给出路的长度w，和经过这条路要交的钱数c。问Bol能从1到达城市n的最短路径为多长。（总共扣的钱数必须不大于coin）
分析：改普通的dij为：只要一边起点的当前花费钱数 + 这条边的花费钱数 <= coin，就让这边终点的信息加入优先队列.(普通的dij是终边的距离有变小才让其加入优先队列)
这题的dij还用到了邻接表。其实这完全可以看做BFS+优先队列View Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define MAXN 10050
using namespace std;
struct ee{
int v,w,c,next;
}edge[MAXN];
struct node{
int u,l,c;
bool operator <(const node &a)const{
return l>a.l;
};
};
int first[105];
priority_queue<node> q;
int K,N,R;
int e;
void init(int n)
{
memset(first,-1,sizeof(first));
e=0;
}
void add(int u,int v,int w,int c)
{
edge[e].v=v;
edge[e].w=w;
edge[e].c=c;
edge[e].next=first[u];
first[u]=e++;
}
int dij(int s,int end)
{
while(!q.empty())
{
q.pop();
}
node a;
a.u=s,a.l=0,a.c=0;
q.push(a);
while(!q.empty())
{
node now=q.top();
q.pop();
int u=now.u;
if(u==end)return now.l;
for(int i=first[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(now.c+edge[i].c<=K)
{
a.u=v,a.l=now.l+edge[i].w,a.c=now.c+edge[i].c;
q.push(a);
}
}
}
return -1;
}
int main()
{
scanf("%d%d%d",&K,&N,&R);
int s,d,l,t;
init(N);
for(int i=0;i<R;i++)
{
scanf("%d%d%d%d",&s,&d,&l,&t);
add(s,d,l,t);
}
printf("%dn",dij(1,N));
}
题意：求1到n路径权值最小值中的最大值
用变形的dij写，其实这个我之前都是用变形的spfa写的，dij不会写，变形的地方原理一样。。
for(int j=1;j<=n;j++)
if(!vis[j]&&d[j]<min(d[k],g[k][j]))
d[j]=min(d[k],g[k][j]);
好吧，贴上变形的dij代码View Code
#include <cstring>
#include <cstdio>
#include <iostream>
#define MAXN 1005
#define INF 1000000000
using namespace std;
int g[MAXN][MAXN];
int d[MAXN],vis[MAXN];
int n,m;
int dij(int s,int end)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
d[i]=g[s][i];
vis[s]=1,d[s]=0;
for(int i=1;i<=n;i++)
{
int maxn=0,k=0;
for(int j=1;j<=n;j++)
if(d[j]>maxn&&!vis[j])
{
maxn=d[j];k=j;
}
if(!k)
break;
vis[k]=1;
for(int j=1;j<=n;j++)
if(!vis[j]&&d[j]<min(d[k],g[k][j]))
d[j]=min(d[k],g[k][j]);
}
return d[n];
}
int main()
{
int tt;
scanf("%d",&tt);
for(int cas=1;cas<=tt;cas++)
{
memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(g[a][b])
g[a][b]=g[b][a]=max(c,g[a][b]);
else g[a][b]=g[b][a]=c;
}
printf("Scenario #%d:n",cas);
printf("%dnn",dij(1,n));
}
}
题意：
给出两只青蛙的坐标A、B，和其他的n-2个坐标，任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路，每一条通路的元素都是这条通路中前后两个点的距离，这些距离中又有一个最大距离。
现在要求求出所有通路的最大距离，并把这些最大距离作比较，把最小的一个最大距离作为青蛙的最小跳远距离。
变形的dijView Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXN 205
using namespace std;
double g[MAXN][MAXN];
struct node{
int x,y;
}p[MAXN];
double d[MAXN];
int vis[MAXN];
int n;
double cul(node a,node b){
return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}
double dij(int s,int end){
for(int i=1;i<=n;i++)
d[i]=g[s][i];
memset(vis,0,sizeof(vis));
vis[s]=1;
for(int i=1;i<=n;i++){
double minc=1000000000;
int k=0;
for(int j=1;j<=n;j++){
if(minc>d[j]&&!vis[j])
{
minc=d[j],k=j;
}
}
if(k==0)break;
vis[k]=1;
for(int j=1;j<=n;j++){
if(!vis[j]&&(d[j]>max(d[k],g[k][j])))
d[j]=max(d[k],g[k][j]);
}
}
return d[end];
}
int main()
{
int cas=1;
while(scanf("%d",&n)==1){
if(!n)break;
int a,b;
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&b);
p[i].x=a,p[i].y=b;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=1000000000;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=cul(p[i],p[j]);
printf("Scenario #%dn",cas++);
printf("Frog Distance = %.3lfnn",dij(1,2));
}
return 0;
}
分析：就是求两点之间的最短距离，不过这题的建图麻烦点。。dij水之View Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define MAXN 205
using namespace std;
double g[MAXN][MAXN];
bool f[MAXN][MAXN];
struct node{
int x,y;
}p[MAXN];
int n;
double walkv,subv;
double d[MAXN];
int vis[MAXN];
double dis(node a,node b)
{
return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}
double dij(int s,int end)
{
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
d[i]=g[s][i];
vis[s]=1;
for(int i=0;i<n;i++)
{
double minc=1000000000;
int k=-1;
for(int j=0;j<n;j++)
if(!vis[j]&&minc>d[j])
{
k=j,minc=d[j];
}
if(k==-1)break;
if(k==end)
return d[k];
vis[k]=1;
for(int j=0;j<n;j++)
if(!vis[j]&&d[k]+g[k][j]<d[j])
d[j]=d[k]+g[k][j];
}
return d[end];
}
int main()
{
scanf("%d%d",&p[0].x,&p[0].y);
scanf("%d%d",&p[1].x,&p[1].y);
n=2;
int a,b;
int m=2;
subv=40*1000.0/60;
walkv=10*1000.0/60;
memset(f,false,sizeof(f));
while(scanf("%d%d",&a,&b)==2)
{
if(a==-1&&b==-1)
{
for(int i=m;i<n-1;i++)
{
g[i][i+1]=g[i+1][i]=dis(p[i],p[i+1])/subv;
f[i][i+1]=f[i+1][i]=true;
}
m=n;
continue;
}
p[n].x=a,p[n].y=b;
n++;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(!f[i][j])
g[i][j]=dis(p[i],p[j])/walkv;
printf("%dn",(int)(dij(0,1)+0.5));
}
分析：每条边的权值=这条边的unit price*这条边的所有子孙节点的和，求一棵树n个节点的(n-1)条边边权之和的最小值。
可以转化为ans = ∑dist[i] * weight[i].(1 <= i <= vn），其中dist[i]为结点i到根结点root(1)的距离，vn为结点数.
这题还有空树的情况。。伤不起啊。。
用SPFA即可View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 50050
#define LL long long
#define INF 10000000000LL
using namespace std;
struct ee{
int v,w,next;
}edge[MAXN*3];
int first[MAXN];
int e;
LL d[MAXN];
int vis[MAXN],q[MAXN];
int cnt[MAXN];
int p[MAXN];
int n,m;
void add(int u,int v,int w){
edge[e].v=v;
edge[e].w=w;
edge[e].next=first[u];
first[u]=e++;
}
LL spfa(int s){
int front=0,rear=0;
memset(vis,0,sizeof(vis));
// memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
d[i]=INF;
q[rear++]=s;
d[s]=0;
vis[s]=1;
while(front!=rear){
int u=q[front++];
if(front>n)front=0;
vis[u]=0;
for(int i=first[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(d[v]>d[u]+edge[i].w){
d[v]=d[u]+edge[i].w;
if(!vis[v]){
q[rear++]=v;
// cnt[v]++;
// if(cnt[v]>n)return -1;//这个用来求是否有负环，有，返回-1
if(rear>n)rear=0;
vis[v]=1;
}
}
}
}
LL ans=0;
for(int i=1;i<=n;i++)
if(d[i]==INF)return -1;
else
ans+=d[i]*p[i];
return ans;
}
int main()
{
freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
int a,b,c;
memset(first,-1,sizeof(first));
e=0;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);add(b,a,c);
}
if(n==0)printf("0n");
else{
LL ans=spfa(1);
if(ans==-1)printf("No Answern");
else
printf("%I64dn",ans);
}
}
return 0;
}
题意：坐汽车旅游，有n个加油站，每个站有自己的油价，假设每个单位距离耗一个单位油。车子邮箱最多能装c单位油。
问从a到b的最小花费
分析：这题要用到DP状态转移的思想，dp[i][j]表示在i站剩余j单位油时的最小花费，增加状态要一点一点的增加，如果把第i个站的油量1-cap一次性增加，会超时，增加了很多不需要的状态。。
算法：变形的dijView Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 1050
#define INF 1000000000
using namespace std;
struct ee{
int v,w,next;
}edge[MAXN*10*2];
int e,first[MAXN];
int dp[MAXN][105];//在i位置剩余j单位油时最少花费
int vis[MAXN][105];
struct node{
int city;//当前城市
int fuel;//当前油剩余量
int cost;//当前花费
bool operator <(const node &a)const{
return cost>a.cost;
};
};
int p[MAXN];
priority_queue<node>q;
int n,m;
void add(int u,int v,int w){
edge[e].v=v;
edge[e].w=w;
edge[e].next=first[u];
first[u]=e++;
}
int dij(int s,int end,int cap){
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
for(int j=0;j<=cap;j++)dp[i][j]=INF;
while(!q.empty())q.pop();
node a;
a.city=s,a.cost=0,a.fuel=0;
q.push(a);
dp[s][0]=0;
vis[s][0]=1;
while(!q.empty()){
node now=q.top();
q.pop();
int u=now.city;
if(u==end)return now.cost;
/* for(int i=now.fuel+1;i<=cap&&!vis[u][i]&&dp[u][i]>dp[u][i-1]+p[u];i++)
{
a.city=now.city;
a.cost=dp[u][i-1]+p[u];
dp[u][i]=dp[u][i-1]+p[u];
a.fuel=i;
q.push(a);
}
*/
int i=now.fuel+1;//只需将油量增一即可，而不是全加上，如上注释代码，全加上会超时，因为增加了许多不需要的状态
if(i<=cap&&!vis[u][i]&&dp[u][i]>dp[u][i-1]+p[u]){
a.city=now.city;
a.cost=dp[u][i-1]+p[u];
dp[u][i]=dp[u][i-1]+p[u];
a.fuel=i;
q.push(a);
}
for(i=first[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
int k=now.fuel-edge[i].w;
if(k>=0&&!vis[v][k]&&dp[v][k]>now.cost){
dp[v][k]=now.cost;
a.city=v;
a.cost=now.cost;
a.fuel=k;
q.push(a);
}
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&p[i]);
int a,b,c;
memset(first,-1,sizeof(first));
e=0;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);add(b,a,c);
}
int tt;
scanf("%d",&tt);
while(tt--){
scanf("%d%d%d",&a,&b,&c);
int ans=dij(b,c,a);
if(ans==-1)printf("impossiblen");
else printf("%dn",ans);
}
return 0;
}
http://blog.sina.com.cn/s/blog_69a101130100jwci.html这个解题报告很好
这题要用c++，用G++会wa
题意：求一个环，环中每点都有一个fun值，还有路上所花时间，求环中所有fun值和/遍历环的时间的最大值
分析:通过二分答案，判断负环，求得答案View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXN 5050
#define INF 1000000000
using namespace std;
struct ee{
int v,w,next;
}edge[MAXN];
int p[MAXN];
int first[MAXN];
int e;
double d[MAXN];
int vis[MAXN],q[MAXN],cnt[MAXN];
int L,P;
void add(int u,int v,int w){
edge[e].v=v;
edge[e].w=w;
edge[e].next=first[u];
first[u]=e++;
}
bool spfa(double ans){
int front=0,rear=0;
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=L;i++)
d[i]=INF;
d[1]=0;
q[rear++]=1;
vis[1]=1;
while(rear!=front){
int u=q[front++];
if(front>L)front=0;
vis[u]=0;
for(int i=first[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(d[v]>d[u]+edge[i].w*ans-p[v]){
d[v]=d[u]+edge[i].w*ans-p[v];
if(!vis[v]){
q[rear++]=v;
if(rear>L)rear=0;
vis[v]=1;
cnt[v]++;
if(cnt[v]>L)return false;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d",&L,&P);
for(int i=1;i<=L;i++)
scanf("%d",&p[i]);
int a,b,c;
memset(first,-1,sizeof(first));
e=0;
for(int i=0;i<P;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
double l=0,r=1000;
double ans,mid;
while(l<=r){
ans=mid;
mid=(l+r)/2;
if(fabs(ans-mid)<1e-6)
break;
if(spfa(mid)){
r=mid;
}
else
l=mid;
}
printf("%.2lfn",ans);
return 0;
}
题意：一个矩形，求左上角到右下角花费的最小时间。。矩形上的点的值代表高度，
已知初始速度v，从a 点到 b 点时，速度变为v(a)*2^(A-B)(A,B为对应点的高度),从 a 到 b 所需的时间为 a 的速度的倒数
，故速度就用倒数表示，，，View Code
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 105
using namespace std;
int g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int V,R,C;
int x[4]={-1,1,0,0};
int y[4]={0,0,1,-1};
struct point{
int x,y;
double v,t;
bool operator < (const point & a)const{
return t>a.t;
}
};
priority_queue<point> q;
double vvv(int x){
double t=1.0;
if(x>=0){
while(x--){
t=t*2;
}
}
else{
while(x++){
t=t/2;
}
}
return t;
}
double BFS(){
memset(vis,false,sizeof(vis));
point a;
a.x=0;a.y=0;a.v=1.0/V;//速度用倒数表示好计算时间
a.t=0;
while(!q.empty()){
q.pop();
}
q.push(a);
while(!q.empty()){
point newp;
newp=q.top();
q.pop();
if(vis[newp.x][newp.y])continue;
vis[newp.x][newp.y]=true;
if(newp.x==R-1&&newp.y==C-1)
return newp.t;
for(int i=0;i<4;i++){
int xx=newp.x+x[i];
int yy=newp.y+y[i];
if(xx>=0&&xx<R&&yy>=0&&yy<C){
if(!vis[xx][yy]){
a.x=xx,a.y=yy;
a.t=newp.v+newp.t;
a.v=newp.v*vvv(g[a.x][a.y]-g[newp.x][newp.y]);
q.push(a);
}
}
}
}
return -1;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d%d%d",&V,&R,&C)){
for(int i=0;i<R;i++)
for(int j=0;j<C;j++){
scanf("%d",&g[i][j]);
}
printf("%.2lfn",BFS());
}
return 0;
}
题意：求1与N的相差的最大值
分析：查分约束，a+c>=b则a--->b的路径的权值为c，这么建图就可以像求最短路径那样写。。。最后d[N]即是结果;
这题要用spfa+栈来写，用spfa+队列会超时。。。也可以用dij+优先队列View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXM 150050
#define MAXN 30050
#define INF 1000000000
using namespace std;
struct eee{
int w,v,next;
}edge[MAXM];
int first[MAXN],d[MAXN],q[MAXN],vis[MAXN];
int e;
int N,M;
void add(int u,int v,int w){
edge[e].v=v;
edge[e].w=w;
edge[e].next=first[u];
first[u]=e++;
}
void init(){
memset(first,-1,sizeof(first));
e=0;
}
int spfa(){
int top=1;
memset(vis,0,sizeof(vis));
for(int i=0;i<=N;i++)d[i]=INF;
d[1]=0;
q[top]=1;
while(top){
int u=q[top--];
vis[u]=0;
for(int i=first[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(d[v]>d[u]+edge[i].w){
d[v]=d[u]+edge[i].w;
if(!vis[v]){
q[++top]=v;
vis[v]=1;
}
}
}
}
return d[N];
}
int main()
{
while(scanf("%d%d",&N,&M)==2){
int a,b,c;
init();
for(int i=0;i<M;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
printf("%dn",spfa());
}
return 0;
}
题意：用floyd求两点之间的最大值中的最小值View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 350
#define INF 1000000000
using namespace std;
int g[MAXN][MAXN];
int N,M,T;
void floyd(){
for(int k=1;k<=N;k++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++){
if(g[i][j]>max(g[i][k],g[k][j])){
g[i][j]=max(g[i][k],g[k][j]);
}
}
}
int main()
{
scanf("%d%d%d",&N,&M,&T);
int a,b,c;
for(int i=0;i<=N;i++)
for(int j=0;j<=N;j++)
g[i][j]=INF;
for(int i=0;i<M;i++){
scanf("%d%d%d",&a,&b,&c);
g[a][b]=c;
}
floyd();
for(int i=0;i<T;i++){
scanf("%d%d",&a,&b);
if(g[a][b]==INF)printf("-1n");
else printf("%dn",g[a][b]);
}
return 0;
}
题解引用Rainy Days
题意：牛之间有绝对的强弱，给出一些胜负关系，问有多少头牛可以确定其绝对排名。
分析：有人说叫闭包传递。这题就是用一种类似于floyd的算法，开始时，如果a胜b则由a到b连一条边。这样所有a能走到的点都是排名在a以后的。所有能走到a的点都是排名在a以前的。用floyd，求出每个点能到达的点。如果有一个点，排名在它之前的和排名在它之后的点之和为n-1，那么它的排名就是确定的。View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 105
using namespace std;
int g[MAXN][MAXN];
int N,M;
int floyd(){
for(int k=1;k<=N;k++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++){
if(g[i][k]&&g[k][j])
g[i][j]=1;
}
int ans=0;
for(int i=1;i<=N;i++){
int cnt=0;
for(int j=1;j<=N;j++){
cnt+=g[i][j]+g[j][i];
}
if(cnt==N-1)ans++;
}
return ans;
}
int main()
{
scanf("%d%d",&N,&M);
memset(g,0,sizeof(g));
int a,b;
for(int i=0;i<M;i++){
scanf("%d%d",&a,&b);
g[a][b]=1;
}
printf("%dn",floyd());
return 0;
}
- 占位未完待续
原文链接: https://www.cnblogs.com/arbitrary/archive/2012/08/18/2645606.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/60073
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
