hdu 6852Path6（最短路+最小割）
2024-10-08 04:23:01
•题意
有n个城市，标号1-n
现花费最小的代价堵路
使得从1号城市到n号城市的路径边长
（注意只是变长不是最长）
堵一条路的代价是这条路的权值
•思路
在堵路以前，从1到n的最小路径当然是最短路
想要路径边长就要在最短路上动手脚
把从1到n的最短路找出来形成一个最短路图，
然后用最小的代价使得最短路图不连通
也就是求这个最短路图的最小割
那怎么建这个最短路图呢？
分别以1和n为源点跑一遍dijkstra,找出每个点到1和n的最短路
设$dis[1][i]$为1到i的最短路，$dis[n][i]$为i到n的最短路
$1->u->v->n$是$1->n$的一条最短路即$dis[1][u]+w[u->v]+dis[n][v]=dis[1][n]$
那么，u->v是1->n最短路上的一条边，加入最短路图中
（由于代码被某人嫌弃太乱，所以对dijkstra和dinic封装了一下...）
•代码
(未封装版)
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair<long long,int>
const int maxn=1e5+;
int n,m;
struct Edge
{
int v;
ll w;
int next;
}de[maxn],fe[maxn],e[maxn]; int head1[maxn],head2[maxn];
int cnt1,cnt2;
void add(int u,int v,ll w)
{
de[++cnt1]={v,w,head1[u]};
head1[u]=cnt1; fe[++cnt2]={u,w,head2[v]};
head2[v]=cnt2;
} ll dis1[maxn],disn[maxn];
bool vis1[maxn],visn[maxn];
priority_queue<P,vector<P>,greater<P> >pq; void dijkstra()
{
while(!pq.empty())
pq.pop();
for(int i=;i<=n;i++)
dis1[i]=INF,vis1[i]=;
dis1[]=;
pq.push(make_pair(,));
while(!pq.empty())
{
int u=pq.top().second;
pq.pop();
if(!vis1[u])
{
vis1[u]=;
for(int i=head1[u];~i;i=de[i].next)
{
int v=de[i].v;
dis1[v]=min(dis1[v],dis1[u]+de[i].w);
pq.push(make_pair(dis1[v],v));
}
}
} while(!pq.empty())
pq.pop();
for(int i=;i<=n;i++)
disn[i]=INF,visn[i]=;
disn[n]=; pq.push(make_pair(,n));
while(!pq.empty())
{
int u=pq.top().second;
pq.pop();
if(!visn[u])
{
visn[u]=;
for(int i=head2[u];~i;i=fe[i].next)
{
int v=fe[i].v;
disn[v]=min(disn[v],disn[u]+fe[i].w);
pq.push(make_pair(disn[v],v));
}
}
}
} int head[maxn],cnt;
int cur[maxn],d[maxn];
void addEdge(int u,int v,ll w)
{
e[++cnt]={v,w,head[u]};
head[u]=cnt; e[++cnt]={u,,head[v]};
head[v]=cnt;
} bool bfs()
{
queue<int> q;
for(int i=;i<=n;i++)
d[i]=-;
d[]=;
q.push();
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(d[v]==-&&e[i].w>)
{
d[v]=d[u]+;
q.push(v);
}
}
}
return d[n]!=-;
} ll dfs(int u,ll flow)
{
ll nowflow=;
if(u==n) return flow;
for(int i=cur[u];~i;i=e[i].next)
{
cur[u]=i;
int v=e[i].v;
if(d[v]==d[u]+&&e[i].w>)
{
ll k=dfs(v,min(flow-nowflow,e[i].w));
if(k)
{
nowflow+=k;
e[i].w-=k;
e[i^].w+=k;
if(nowflow==flow)
break;
}
}
}
if(!nowflow) d[u]=-;
return nowflow;
} ll Dinic()
{
ll ans=;
while(bfs())
{
for(int i=;i<=n;i++)
cur[i]=head[i]; ans+=dfs(,INF);
}
return ans;
} void Init()
{
mem(head1,-);
mem(head2,-);
mem(head,-);
cnt1=cnt2=cnt=-;
} int main()
{
// freopen("C:\\Users\\14685\\Desktop\\C++workspace\\in&out\\contest","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
Init();
for(int i=;i<=m;i++)
{
int u,v;
ll w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
} dijkstra(); for(int u=;u<=n;u++)
{
for(int i=head1[u];~i;i=de[i].next)
{
int v=de[i].v;
if(dis1[u]+disn[v]+de[i].w==dis1[n])
{
// printf("***%d %d %d\n",u,v,de[i].w);
addEdge(u,v,de[i].w);
}
}
} printf("%lld\n",Dinic());
}
}(封装版)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair<ll,int>
#define INF 0x3f3f3f3f3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e5+;
int n,m;
struct Edge
{
int v;
ll w;
int next;
}G[maxn<<],e[maxn<<];
int dhead[maxn],dcnt;
void addEdge(int u,int v,ll w)
{
G[++dcnt]={v,w,dhead[u]};
dhead[u]=dcnt;
} struct Dij
{
ll dis[][maxn];
bool vis[maxn];
priority_queue<pli,vector<pli>,greater<pli> > q;
void dij(int s,int n,bool ok)
{
for(int i=;i<=n;i++)
dis[ok][i]=INF,vis[i]=;
dis[ok][s]=;
q.push({,s});
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])
continue;
vis[u]=;
for(int i=dhead[u];~i;i=G[i].next)
{
///偶数是正向边,ok=true是正向边
if(ok && i&)
continue;
///奇数是反向边,ok=false是反向边
if(!ok && !(i&))
continue; int v=G[i].v;
ll w=G[i].w;
if(dis[ok][v]>dis[ok][u]+w)
{
dis[ok][v]=dis[ok][u]+w;
if(!vis[v])
q.push({dis[ok][v],v});
}
}
}
}
}dij; int head[maxn],cnt;
void add(int u,int v,ll w)
{
e[++cnt]={v,w,head[u]};
head[u]=cnt;
}
struct Dinic
{
int cur[maxn],d[maxn];
int s=,t=n;
bool bfs()
{
queue<int> q;
for(int i=;i<=n;i++)
d[i]=-;
d[]=;
q.push();
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(d[v]==-&&e[i].w>)
{
d[v]=d[u]+;
q.push(v);
}
}
}
return d[n]!=-;
} ll dfs(int u,ll flow)
{
ll nowflow=;
if(u==n) return flow;
for(int i=cur[u];~i;i=e[i].next)
{
cur[u]=i;
int v=e[i].v;
if(d[v]==d[u]+&&e[i].w>)
{
ll k=dfs(v,min(flow-nowflow,e[i].w));
if(k)
{
nowflow+=k;
e[i].w-=k;
e[i^].w+=k;
if(nowflow==flow)
break;
}
}
}
if(!nowflow) d[u]=-;
return nowflow;
} ll din()
{
ll ans=;
while(bfs())
{
for(int i=;i<=n;i++)
cur[i]=head[i]; ans+=dfs(,INF);
}
return ans;
}
}_din; void Init()
{
mem(dhead,-);
dcnt=-;
mem(head,-);
cnt=-;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
Init();
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int u,v;
ll w;
scanf("%d%d%lld",&u,&v,&w);
///跑1到其他点的最短路 加正向边
addEdge(u,v,w);
///跑n到其他点的最短路 加反向边
addEdge(v,u,w);
} dij.dij(,n,true);
dij.dij(n,n,false); for(int u=;u<=n;u++)
{
for(int i=dhead[u];~i;i=G[i].next)
{
int v=G[i].v;
ll w=G[i].w;
if(dij.dis[][u]+dij.dis[][v]+w==dij.dis[][n])
{
add(u,v,w);
add(v,u,);
}
}
}
printf("%lld\n",_din.din());
}
}
最新文章
- H5实现摇一摇技术总结
- 分享一个批量导出当前实例下的所有linkedserver脚本
- java二维数组的常见初始化
- （四）装饰模式-C++实现
- $.ajax()方法详解及实例
- nyoj CO-PRIME 莫比乌斯反演
- ODI中显示us7ascii字符集的测试
- Rabbit MQ安装配置及常见问题
- java.net.MulticastSocket Example--reference
- U8800安装软件显示无效的URI问题
- 《零基础学习Python》01
- （Problem 28）Number spiral diagonals
- js_DOM属性
- obj-c编程04:类的继承
- oracle exp、imp实现导出导入
- EntityFramwork所有 SSDL 项目都必须以同一提供程序为目标。ProviderManifestToken“2008”不同于以前遇到的“2005”
- Spring自学教程-jabc编程详解、RowMapper使用(三)
- Java父线程(或是主线程)等待所有子线程退出
- HTML DOM innerHTML 属性及实现图片连续播放
- SlidingMenu第三篇 --- SlidingMenu使用介绍