最近实在不知道干些什么，感觉自己除了水题什么都不会做，算了去刷一刷图论的水题吧本来想合起来一起发，想了想太长的话以后看起来也不方便，题目所以今天晚上就先发了dij部分，由上到下由易变难。
1.POJ 2387 Til the Cows Come Home（优先队列优化+邻接表）
2.poj 1502 (最短路)
3.POJ3268-Silver Cow Party-（优先队列优化+邻接表）
4.poj 1511 Invitation Cards（优先队列+dij+链向式前向星存图）
5.Heavy Transportation POJ - 1797（优先队列优化+邻接表）
6.poj2253（dij变形+优先队列）
7.hdu4725The Shortest Path in Nya Graph（建图建图建图+dij+优先队列优化）
dijk部分：
3月23日
1.POJ 2387 Til the Cows Come Home
很典型的板子题，问从1点到n点的最小花费（使用优先队列进行优化）
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 2010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int t,n;
bool visited[maxn];
int dis[maxn];
struct wazxy{
int v,val;
wazxy(int v1,int e1){v=v1;val=e1;}
};
vector<wazxy> a[maxn];
struct node{
int id,dis;
node(int a,int b){id=a,dis=b;}
bool operator < (const node & a)const
{return dis>a.dis;}
};
void dij(){
int s=1;
dis[s]=0;
priority_queue<node>q;
q.push(node(s,dis[s]));
while(!q.empty()){
node temp=q.top();
q.pop();
if(visited[temp.id]) continue;
visited[temp.id]=true;
for(int i=0;i<a[temp.id].size();i++){
wazxy node1=a[temp.id][i];
if(visited[node1.v]) continue;
if(dis[node1.v]>node1.val+temp.dis){
dis[node1.v]=node1.val+temp.dis;
q.push(node(node1.v,dis[node1.v]));
}
}
}
printf("%d",dis[n]);
}
int main()
{
cin>>t>>n;
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
while(t--){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
a[x].push_back(wazxy(y,v));
a[y].push_back(wazxy(x,v));
}
dij();
return 0;
}
3月24号
2.poj 1502 (最短路)
题目很坑爹：大致意思是从起点找出到每个点的最短距离，然后从到每个点的最短距离中找出一个最大值输出
找了一下午的bug，原因竟然是再一次的忘记调用dij函数md
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 110
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int n;
int maps[maxn][maxn];
int visited[maxn],dis[maxn];
void init(){
memset(maps,MaxN,sizeof(maps));
for(int i=0;i<maxn;i++) maps[i][i]=0;
}
void dij(){
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++) dis[i]=maps[1][i];
for(int i=1;i<=n;i++){
int imin=MaxN,x;
for(int f=1;f<=n;f++){
if(!visited[f]&&dis[f]<=imin){
x=f;
imin=dis[f];
}
}
visited[x]=true;
for(int f=1;f<=n;f++){
if(!visited[f]&&dis[f]>dis[x]+maps[x][f]){
dis[f]=dis[x]+maps[x][f];
}
}
}
}
int main()
{
char a[10];
while(scanf("%d",&n)!=EOF){
init();
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
scanf("%s",a);
if(a[0]!='x') maps[i][j]=maps[j][i]=atoi(a);
}
}
}
// for(int i=1;i<=n;i++){
// for(int f=1;f<=n;f++){
// cout<<maps[i][f]<<" ";
// }
// cout<<endl;
// }
int imax=0;
dij();
for(int i=1;i<=n;i++){
imax=max(imax,dis[i]);
// cout<<dis[i]<<endl;
}
cout<<imax<<endl;
return 0;
}
3.POJ3268-Silver Cow Party-（Dijstra）
题目大意：让你求每个点到某个点x距离的最短路+x点在返回原点路径的最短路之和，找出其中和的最大值
dij+了队列优化才险些过去（735ms）
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
struct rule{
int u,v,cost;
rule(int a,int b,int c){u=a,v=b,cost=c;}
};
int dis[maxn];
bool visited[maxn];
int n,m,k;
int sum[maxn];
vector <vector<rule> > a;
struct node{
int n,dis;
node(int a,int b){n=a,dis=b;}
bool operator < (const node & a)const
{return dis>a.dis;}
};
void init(){
a.resize(maxn);
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
}
void dij(int x){
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
dis[x]=0;
priority_queue<node> q;
q.push(node(x,0));
while(!q.empty()){
node temp=q.top();
q.pop();
if(visited[temp.n]) continue;
visited[temp.n]=true;
for(int i=0;i<a[temp.n].size();i++){
rule node1=a[temp.n][i];
if(visited[node1.v]) continue;
if(dis[node1.v]>node1.cost+temp.dis){
dis[node1.v]=node1.cost+temp.dis;
q.push(node(node1.v,dis[node1.v]));
}
}
}
}
int main()
{
cin>>n>>m>>k;
init();
for(int i=0;i<m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x].push_back(rule(x,y,z));
}
dij(k);
for(int i=1;i<=n;i++) sum[i]+=dis[i];
for(int i=1;i<=n;i++){
dij(i);
sum[i]+=dis[k];
}
int imax=0;
for(int i=1;i<=n;i++){
imax=max(imax,sum[i]);
}
cout<<imax<<endl;
return 0;
}
3月25日：
4.poj 1511 Invitation Cards（优先队列+dij+链向式前向星存图）
其实这个题应该是昨天刷完的，跟上面的题可以说是一模一样，只是数据量太大了，当然，我继续用了上一题的方法，发现超时，以为是vector的原因，换了链向式前向星存图，发现还是超时，然后就继续优化读入函数等一切可以降低复杂度的操作，发现仍然超时（心态崩了，不写了）于是查了一下题解，竟然还有反向加边这种操作，心态炸裂：
因为本人并不喜欢函数传参这种操作，所以直接用了两个dij，复制粘贴
题解：
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
struct rule{
int v,cost,next;
}edge[maxn],edge1[maxn];
int dis[maxn];
bool visited[maxn];
int n,m,k;
ll sum;
int head[maxn];
int head1[maxn];
struct node{
int n,dis;
node(int a,int b){n=a,dis=b;}
bool operator < (const node & a)const
{return dis>a.dis;}
};
int cnt=0,cnt1;
inline void add(int u,int v,int w){
edge[cnt].cost=w;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
inline void add1(int u,int v,int w){
edge1[cnt1].cost=w;
edge1[cnt1].v=v;
edge1[cnt1].next=head1[u];
head1[u]=cnt1++;
}
inline void dij(int x){
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
dis[x]=0;
priority_queue<node> q;
q.push(node(x,0));
while(!q.empty()){
node temp=q.top();
q.pop();
if(visited[temp.n]) continue;
visited[temp.n]=true;
for(int i=head[temp.n];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(visited[v]) continue;
if(dis[v]>temp.dis+edge[i].cost){
dis[v]=temp.dis+edge[i].cost;
q.push(node(v,dis[v]));
}
}
}
}
inline void dij1(int x){
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
dis[x]=0;
priority_queue<node> q;
q.push(node(x,0));
while(!q.empty()){
node temp=q.top();
q.pop();
if(visited[temp.n]) continue;
visited[temp.n]=true;
for(int i=head1[temp.n];i!=-1;i=edge1[i].next){
int v=edge1[i].v;
if(visited[v]) continue;
if(dis[v]>temp.dis+edge1[i].cost){
dis[v]=temp.dis+edge1[i].cost;
q.push(node(v,dis[v]));
}
}
}
}
inline void init(){
memset(head,-1,sizeof(head));
memset(head1,-1,sizeof(head1));
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
sum=0;
cnt=0;
cnt1=0;
}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main()
{
int t;
cin>>t;
while(t--){
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++){
int x,y,z;
x=read(),y=read(),z=read();
add(x,y,z);
add1(y,x,z);
}
// for(int i=0;i<cnt;i++) cout<<edge[i].cost<<endl;
dij(1);
// cout<<dis[1]<<endl;
for(int i=1;i<=n;i++) sum+=dis[i];
dij1(1);
for(int i=1;i<=n;i++) sum+=dis[i];
printf("%lld\n",sum);
}
return 0;
}
5.Heavy Transportation POJ - 1797
题意：从1点到n点运送货物，每个每两个地方用桥梁链接，每个桥梁都有自己的最大承重，问：最大能运送多重的货物到达目的地。
注意是个无向图，注意每个例子之间多输出一行空行
这个题也是一个并不难的图论题，只不过就是把条件这里一块改了一下，当然，我是不会告诉你我这个题在条件这一块地方wa了好多次。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
struct wazxy{
int to,val;
wazxy(int a,int b){to=a,val=b;}
};
vector<vector<wazxy> > a;
struct node{
int id,dis;
node(int a,int b){id=a,dis=b;}
bool operator < (const node & a)const
{return dis<a.dis;}
};
bool visited[maxn];
int dis[maxn];
void init(){
memset(visited,false,sizeof(visited));
for(int i=0;i<=maxn;i++) dis[i]=0;
a.resize(maxn);
a.clear();
}
int n,m;
void dij(){
dis[1]=MaxN;
priority_queue<node> q;
q.push(node(1,MaxN));
while(!q.empty()){
node temp=q.top();
q.pop();
if(visited[temp.id]) continue;
visited[temp.id]=true;
for(int i=0;i<a[temp.id].size();i++){
int to=a[temp.id][i].to;
if(visited[to]) continue;
if(dis[to]<min(temp.dis,a[temp.id][i].val)){
dis[to]=min(temp.dis,a[temp.id][i].val);
q.push(node(to,dis[to]));
}
}
}
}
int main()
{
int t;
cin>>t;
int ans=1;
while(t--){
init();
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x].push_back(wazxy(y,z));
a[y].push_back(wazxy(x,z));
}
dij();
printf("Scenario #%d:\n",ans++);
printf("%d\n",dis[n]);
printf("\n");
}
return 0;
}
6.poj2253（dij变形+优先队列）
题意：就是找出从一个点到另一个点的所有道路，每条道路里都有都有最长的边，然后再从所有最长的边中找出最短的来输出。哦是不是很绕，反正我晕了一会。
跟头顶上的题目十分相似。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
struct wazxy{
double to,val;
wazxy(double a,double b){to=a,val=b;}
};
vector<vector<wazxy> > a;
struct node{
int id;
double dis;
node(int a,double b){id=a,dis=b;}
bool operator < (const node & a)const
{return dis>a.dis;}
};
bool visited[maxn];
double dis[maxn];
void init(){
memset(visited,false,sizeof(visited));
for(int i=0;i<maxn;i++) dis[i]=MaxN;
a.resize(maxn);
a.clear();
}
int n;
void dij(){
dis[1]=MaxN;
priority_queue<node> q;
q.push(node(1,0));
while(!q.empty()){
node temp=q.top();
q.pop();
double d=temp.dis;
int u=temp.id;
if(visited[u]) continue;
for(int i=0;i<a[u].size();i++){
wazxy node1=a[u][i];
int v=node1.to;
double w=node1.val;
if(visited[v]) continue;
if(dis[v]>max(w,d)){
dis[v]=max(w,d);
// cout<<dis[v]<<endl;
q.push(node(v,dis[v]));
}
}
}
}
struct name{
int x,y;
}s[210];
inline double getlen(double x,double y,double x1,double y1){
return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
int main()
{
int cnt=0;
while(cin>>n&&n){
init();
cnt++;
for(int i=1;i<=n;i++){
cin>>s[i].x>>s[i].y;
}
for(int i=1;i<=n;i++){
for(int f=i+1;f<=n;f++){
double temp=getlen(s[i].x,s[i].y,s[f].x,s[f].y);
a[i].push_back(wazxy(f,temp));
a[f].push_back(wazxy(i,temp));
}
}
dij();
printf("Scenario #%d\n",cnt);
printf("Frog Distance = %.3f\n\n",dis[2]);
//for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
}
return 0;
}
7.hdu4725The Shortest Path in Nya Graph（建图建图建图+dij+优先队列优化）
搬运一下别人的翻译：n个点，m条边，以及相邻层之间移动的代价c，给出每个点所在的层数，以及m条边，每条边有u，v，c，表示从节点u到v（无向），并且移动的代价 c ，问说从 1 到 n 的代价最小是多少。
mdmdmd建图看别人的建图看了半小时才看懂，然后就是套模板了
其实就是把图层也看成点，对应的编号分别为n+1到n+n
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int head[maxn];
struct wazxy{
int v,w,next;
}edge[maxn];
bool visited[maxn];
bool vis[maxn];
int dis[maxn];
int f[maxn];
int n,m,c;
int cnt;
void init(){
cnt=0;
memset(visited,false,sizeof(visited));
memset(vis,false,sizeof(vis));
memset(head,-1,sizeof(head));
memset(dis,MaxN,sizeof(dis));
}
void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
struct node{
int n,dis;
node(int a,int b){n=a,dis=b;}
bool operator < (const node & a)const
{return dis>a.dis;}
};
inline void dij(){
dis[1]=0;
priority_queue<node> q;
q.push(node(1,0));
while(!q.empty()){
node temp=q.top();
q.pop();
if(visited[temp.n]) continue;
visited[temp.n]=true;
for(int i=head[temp.n];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(visited[v]) continue;
if(dis[v]>temp.dis+edge[i].w){
dis[v]=temp.dis+edge[i].w;
q.push(node(v,dis[v]));
}
}
}
}
int main()
{
int t;
cin>>t;
int ans=1;
while(t--){
init();
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++){
scanf("%d",&f[i]);
vis[f[i]]=true;
}
for(int i=1;i<n;i++){
if(vis[i]&&vis[i+1]){
add(n+i,n+i+1,c);
add(n+i+1,n+i,c);
}
}
for(int i=1;i<=n;i++){
add(n+f[i],i,0);
if(f[i]>1) add(i,n+f[i]-1,c);
if(f[i]<n) add(i,n+f[i]+1,c);
}
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dij();
printf("Case #%d: ",ans++);
if(dis[n]<MaxN) printf("%d\n",dis[n]);
else printf("-1\n");
}
return 0;
}
京公网安备 11010502036488号