BZOJ 1266 [AHOI2006] 上学路线 route

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1266

题意：一张无向图，边有时间，费用两个权值，第一问从 1 到 n 最短时间，第二问删除一些边使得最短时间变长的最小权值....

第一问随便最短路... 为了方便搞了个 floyd....

考虑第二问怎么搞... 其实是个萨博题... 却想了好半天.... 最短路变长只要旧最短路走不通就行了... 那么针对旧最短路建图，最小割，结束...

评论区说有重边... 实际上并没有，或者不需要处理.. 代码如下：

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 510
#define M 124800
#define inf 210000000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'|ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct zgz
{
	int next,to,val;
}edge[M<<1];
int cnt=2,head[M<<1];
void add(int from,int to,int val)
{
	edge[cnt].to=to;
	edge[cnt].val=val;
	edge[cnt].next=head[from];
	head[from]=cnt++;
}
void insert(int from,int to,int val)
{add(from,to,val);add(to,from,0);}
int n,m,f[N][N],ans,S,T;
int a[M],b[M],c[M],d[M];
int dis[N];
queue<int> q;
bool bfs()
{
	memset(dis,0,sizeof(dis));
	dis[S]=1,q.push(S);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=edge[i].next)
		{
			int to=edge[i].to,val=edge[i].val;
			if(!dis[to]&&val)
			{
				dis[to]=dis[x]+1;
				q.push(to);
			}
		}
	}
	if(dis[T])return 1;
	return 0;
}
int dfs(int x,int v)
{
	if(x==T||v==0)return v;
	int ret=0;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to,val=edge[i].val;
		if(dis[to]==dis[x]+1)
		{
			int f=dfs(to,min(v,val));
			edge[i].val-=f,edge[i^1].val+=f;
			v-=f,ret+=f;
			if(v==0)break;
		}
	}
	if(ret==0)dis[x]=-1;
	return ret;
}
int main()
{
	n=read(),m=read();S=1,T=n;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=m;i++)
	{
		a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
		f[a[i]][b[i]]=f[b[i]][a[i]]=c[i];
	}
	for(int i=1;i<=n;i++)f[i][i]=0;
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	printf("%d\n",f[1][n]);
	for(int i=1;i<=m;i++)
	{
		int x=a[i],y=b[i],z=c[i];
		if(f[1][x]+f[y][n]+z==f[1][n])
		insert(x,y,d[i]);
		if(f[1][y]+f[x][n]+z==f[1][n])
		insert(y,x,d[i]);
	}
	while(bfs())ans+=dfs(S,inf);
	printf("%d",ans);
}

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 510

#define M 124800

#define inf 210000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch>'9'|ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

struct zgz

{

int next,to,val;

}edge[M<<1];

int cnt=2,head[M<<1];

void add(int from,int to,int val)

{

edge[cnt].to=to;

edge[cnt].val=val;

edge[cnt].next=head[from];

head[from]=cnt++;

}

void insert(int from,int to,int val)

{add(from,to,val);add(to,from,0);}

int n,m,f[N][N],ans,S,T;

int a[M],b[M],c[M],d[M];

int dis[N];

queue<int> q;

bool bfs()

{

memset(dis,0,sizeof(dis));

dis[S]=1,q.push(S);

while(!q.empty())

{

int x=q.front();q.pop();

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(!dis[to]&&val)

{

dis[to]=dis[x]+1;

q.push(to);

}

if(dis[T])return 1;

return 0;

}

int dfs(int x,int v)

{

if(x==T||v==0)return v;

int ret=0;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(dis[to]==dis[x]+1)

{

int f=dfs(to,min(v,val));

edge[i].val-=f,edge[i^1].val+=f;

v-=f,ret+=f;

if(v==0)break;

}

if(ret==0)dis[x]=-1;

return ret;

}

int main()

{

n=read(),m=read();S=1,T=n;

memset(f,0x3f,sizeof(f));

for(int i=1;i<=m;i++)

{

a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();

f[a[i]][b[i]]=f[b[i]][a[i]]=c[i];

}

for(int i=1;i<=n;i++)f[i][i]=0;

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

printf("%d\n",f[1][n]);

for(int i=1;i<=m;i++)

{

int x=a[i],y=b[i],z=c[i];

if(f[1][x]+f[y][n]+z==f[1][n])

insert(x,y,d[i]);

if(f[1][y]+f[x][n]+z==f[1][n])

insert(y,x,d[i]);

}

while(bfs())ans+=dfs(S,inf);

printf("%d",ans);

}

zgz233

zgz233

BZOJ 1266 [AHOI2006] 上学路线 route

l1ll5

Comments | NOTHING