图论综合练（最短路）

图论基本上都是考思维的，啥spaf呀，krushkal呀，tranj呀，把模板练好，剩下的就是练思维了...

一：最短路：

题目要求使其中的边增加，使得改变后的图中最短路最大。

显然，我们不能增加原图中非最短路的边，因为增加没有意义，改变后最短路与原图的一样，增量为0.

那我们就只考虑园图中是最短路的边就行了。数据范围小，一一枚举边，重新跑最短路即可。

注意细节，这里是记录了最短路的路径了：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5100;
long long n,m,link[maxn],tot,zhi[maxn],vis[maxn],dis[maxn],id[maxn],o,maxx,mazx;
struct bian
{
long long y,next,v;
};
bian a[maxn*2];
inline long long read()
{
long long x=0,ff=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') ff=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*ff;
}
inline void spaf()
{
queue<int>q;
memset(dis,127,sizeof(dis));
dis[1]=0;vis[1]=1;q.push(1);
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=0;
for(int i=link[x];i;i=a[i].next)
{
int y=a[i].y;
if(dis[y]>dis[x]+a[i].v)
{
dis[y]=dis[x]+a[i].v;zhi[y]=x;
if(!vis[y]) q.push(y),vis[y]=1;
}
}
}
}
inline void spaf1()
{
queue<int>q;
memset(dis,127,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;vis[1]=1;q.push(1);
while(!q.empty())
{
int x=q.front();vis[x]=0;q.pop();
for(int i=link[x];i;i=a[i].next)
{
int y=a[i].y;
if(id[x]&&id[y]&&dis[y]>dis[x]+a[i].v*2)
{
dis[y]=dis[x]+a[i].v*2;
if(!vis[y]) q.push(y),vis[y]=1;
}
else if((!id[x]||!id[y])&&dis[y]>dis[x]+a[i].v)
{
dis[y]=dis[x]+a[i].v;
if(!vis[y]) q.push(y),vis[y]=1;
}
}
}
}
inline void add(int x,int y,int v)
{
a[++tot].v=v;
a[tot].y=y;
a[tot].next=link[x];
link[x]=tot;
}
int main()
{
//
freopen("1.in","r",stdin);
n=read();m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),v=read();
add(x,y,v);add(y,x,v);
}
spaf();maxx=dis[n];
o=n;
while(o!=1)
{
id[o]=1;id[zhi[o]]=1;
spaf1();mazx=max(mazx,dis[n]);
id[o]=0;id[zhi[o]]=0;
o=zhi[o];
}
cout<<mazx-maxx<<endl;
return 0;
}

下一题：

这个题一下子就提高了不少，我们读一遍题，理一下题意：也就是说，奶牛不跑最短路，在美味值允许的前提下，去有草捆的牧场，然后回家。

我们设dis1表示终点到i点的距离，dis2表示x草捆到i点的距离，那我们就要比较dis1[x]+dis2[i]-dis1[i]与z的大小，简而言之，如果dis1[x]+dis2[i]-dis1[i]<=z那么久符合条件。

既然如此，那我们看一下哪些是定值（并且好求），显然dis1[x]与dis1[i]我们可以从终点跑一边spaf求出，而dis2[i]就需要枚举每个x求出不同的值，这就是暴力！既然dis1[x]与dis1[i]好求，那我们模仿参变量分离一样，将不等式换一种形式，dis1[x]+dis2[i]-z<=dis1[i]，这样右边的变量就是一个定值了。我们剩下的任务就是找到一个草垛使得dis1[x]+dis2[i]-z最小，看到这里，我们终于闻到了最短l路的气息，因为最短路不就是要跑一个最短距离吗？可到这还不行，我们继续想，怎样使得跑的一个路径是dis1[x]+dis2[i]-z呢？dis2[i]还能想到，是某个草捆到一个点的距离，那dis1[x]-z怎么办呢？没有办法，那就自己造呀!这就是这个题的精妙之处，我们建一个超级汇点n+1，使得n+1与每一个草捆都连上一个单向边，

边权就为dis1[x]-z这样从超级汇点跑到一个点的距离就为dis1[x]-z+dis2[i]，而且还是最小的，巧妙的解决了这个问题。从超级汇点跑一个spaf之后就简单了，一个一个枚举比较与dis1[i]的大小即可，也没什么细节，实现起来很简单，也就是难想了点。其实启示还是很多的，比如分析题目需要的条件与排除冗杂信息，找到最优的解决方案，此题中的找到最小的dis1[x]+dis2[i]-z就是如此。还有如果实在没有办法依据题中的实现，那就自己创造！超级汇点就是干这个用的。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
int link[51000],tot,n,m,k,dis[51000],vis[51000],c[51000],id[51000];
struct bian
{
int y,v,next;
};
bian a[maxn*2];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') ff=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*ff;
}
inline void add(int x,int y,int v)
{
a[++tot].y=y;
a[tot].v=v;
a[tot].next=link[x];
link[x]=tot;
}
inline void spaf(int s)
{
queue<int>q;q.push(s);
memset(dis,127,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;vis[s]=1;
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=0;
for(int i=link[x];i;i=a[i].next)
{
int y=a[i].y;
if(dis[y]>dis[x]+a[i].v)
{
dis[y]=dis[x]+a[i].v;
if(!vis[y]) vis[y]=1,q.push(y);
}
}
}
}
int main()
{
//freopen("1.in","r",stdin);
n=read();m=read();k=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),v=read();
add(x,y,v);add(y,x,v);
}
spaf(n);
for(int i=1;i<=n;i++) c[i]=dis[i];
for(int i=1;i<=k;i++)
{
int x=read(),z=read();
add(n+1,x,c[x]-z);
}
spaf(n+1);
for(int i=1;i<n;i++)
{
if(dis[i]<=c[i]) cout<<1<<endl;
else
cout<<0<<endl;
}
return 0;
}

下一个：

有点水，不过考的更多的是实践。也就是代码能力。

记得以前在OJ上做过类似的问题，一个航线上，到哪的价格一样，那就一个一个建边。边权都标成一样的价格就行。

傻傻的我面对这巨大的边的数量还在用邻接表，哭死！！！

之后改成邻接矩阵存储方便，而且不用冒着邻接表爆空间的风险（因为你不知道要开多大的空间）。

最短路容易解决，跑一边spaf即可。

可最少的城市呢？我们把一条航线上的城市用许多边代替，那我们建完图后，没有信息了呀！

这时就要在定义结构体了，记录每个边的同时记录他经过的城市数。之后再spaf中一起迭代。

我们先要保证费用最少，在此前提下经过最少的城市。于是当当前迭代的边与与最短路一样时，可以用来更新最小的城市。

诸如此类的问题，都可以这样解决。

也就是这个代码：else if(dis[i]==dis[x]+a[x][i].v&&...)  ...；

这样就保证在最短路的前提下进行其他的操作，求最少边数呀之类的。

好了，就这样结束了：

代码：

#include<bits/stdc++.h>
#define ll long long
const ll maxn=1005;
using namespace std;
ll A,B,N,n,b[maxn],dis[maxn],city[maxn],vis[maxn];
struct bian
{
ll v,cnt;
};
bian a[maxn][maxn];
inline ll read()
{
ll x=0,ff=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') ff=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*ff;
}
inline void SPAF()
{
queue<int>q;q.push(A);
memset(dis,127,sizeof(dis));
memset(city,127,sizeof(city));
dis[A]=0;city[A]=0;vis[A]=1;
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=0;
for(int i=1;i<=n;i++)
{
if(a[x][i].v<1e18)
{
if(dis[i]>dis[x]+a[x][i].v)
{
dis[i]=dis[x]+a[x][i].v;city[i]=city[x]+a[x][i].cnt;
if(!vis[i]) q.push(i),vis[i]=1;
}
else if(dis[i]==dis[x]+a[x][i].v&&city[i]>city[x]+a[x][i].cnt)
city[i]=city[x]+a[x][i].cnt;
}
}
}
}
int main()
{
//freopen("1.in","r",stdin);
A=read();B=read();N=read();
for(int i=1;i<maxn;i++)
for(int j=1;j<maxn;j++) a[i][j].v=a[i][j].cnt=1e18;
for(int i=1;i<=N;i++)
{
ll x=read(),y=read();
for(int j=1;j<=y;j++) b[j]=read(),n=max(n,b[j]);
for(int j=1;j<=y;j++)
for(int k=j+1;k<=y;k++)
{
if(x<a[b[j]][b[k]].v)
a[b[j]][b[k]].v=x,a[b[j]][b[k]].cnt=k-j;
else if(x==a[b[j]][b[k]].v&&k-j<a[b[j]][b[k]].cnt) a[b[j]][b[k]].cnt=k-j;
}
}
SPAF();
if(dis[B]==dis[0]) cout<<-1<<' '<<-1<<endl;
else
cout<<dis[B]<<' '<<city[B]<<endl;
return 0;
}

 下一题：真是毒瘤题：

此题真正的让我对最短路有了新的认识。

以前只理解最短路跑最短距离，现在才知道最短路只是一个工具，边权不一定是距离，可以使任何东西，这个才是最短路的真正魅力。

例如此题从1到n最小的警告次数，那我们将边权设置为通过这条边的警告次数，这样跑一个spaf答案就显而易见了。

但是这样设置的前提是通过每条边的警告次数是定值我们可以预处理出来，才可以这样使用，不过此题可以按照题目中的例子模拟一下就可以预处理出边权。

PS：有重边时，要标记边，标记点会wrong！！！

其实在上上一题中，我们已经用其他的东西单当做边权，而这道题只是更彻底的变化，为了就是打破我们那个最短路只能求距离的概念.但如果将边权换成其他量时，注意这些量必须是定值，可以简单的预处理出来.