题面

题意:给你n(2w5)个点,m条边(7w5)有k(1e3)辆车停在某些点上的,然后他们都想尽快去1号点,同时出发,同一个点不允许同时经过,

如果多辆车同时到达一个点,他们就会堵塞,这时候只能选择通过一辆车,其他车相当于就地爆炸

问最后能有多少车到1号点

题解:想象如果2辆车的最短路不相交,那么他们就互相之间没有了影响,再想象对于一般的图,如何控制度数的,显然有一个网络流的做法

可以走的边就连,度数为1,现在我们考虑每部分最短路长度相等的点集才会受到影响.如果2个点到1的最短路长度一样,那么他们才

可能会经过同一个点,于是针对每一堆最短路一样的,单独建图,累加他们的和就是答案.

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define lld long long
using namespace std;
#define N 30007
#define M 100007
#define inf 100000000000000LL
namespace Dinic
{
int head[N],head2[N],p=;
struct Rec
{
int go,nex;
lld c;
}eg[M*],e[M*];
void build(int a,int b,lld c)
{
//printf("%d %d %d\n",a,b,c);
eg[++p]=(Rec){b,head[a],-c};
head[a]=p;
eg[++p]=(Rec){a,head[b],};
head[b]=p;
}
lld dis[N],ans;
int Q[N],s[N],S,T,stop;
bool bfs()
{
memset(dis,,sizeof(dis));
dis[T]=;
Q[]=T;
for (int p1=,p2=;p1<=p2;p1++)
{
for (int i=head[Q[p1]];i;i=eg[i].nex)
if (eg[i^].c<&&!dis[eg[i].go])
{
dis[eg[i].go]=dis[Q[p1]]+;
Q[++p2]=eg[i].go;
}
}
if (!dis[S]) return false;
memcpy(head2,head,sizeof(head));
return true;
}
bool dinic(int p,int top)
{
if (p==T)
{
lld x=inf;
for (int i=;i<=top-;i++) if (-eg[s[i]].c<x) x=-eg[s[i]].c,stop=i;
for (int i=;i<=top-;i++) eg[s[i]].c+=x,eg[s[i]^].c-=x;
ans+=x;
return true;
}
for (int &i=head2[p];i;i=eg[i].nex)
{
if (eg[i].c<&&dis[eg[i].go]==dis[p]-)
{
s[top]=i;
if (dinic(eg[i].go,top+)&&top!=stop) return true;
}
}
return false;
}
lld ask()
{
ans=;
while (bfs()) dinic(S,);
return ans;
}
void init(int _S,int _T){
S=_S,T=_T;
}
}
using namespace Dinic;
void clear()
{
p=;
memset(head,,sizeof(head));
}
int n,m,ss,tt,why=;
long long diss[N];
void addedge(int a,int b,lld c)
{
p++;
e[p].go=b;
e[p].c=c;
e[p].nex=head[a];
head[a]=p;
}
void dijkstra()
{
priority_queue<pa,vector<pa>,greater<pa> >q;
for (int i=;i<=n;i++) diss[i]=inf;
diss[]=;
q.push(make_pair(,));
while (!q.empty())
{
int now=q.top().second;
q.pop();
for (int i=head[now];i;i=e[i].nex)
if(diss[now]+e[i].c<diss[e[i].go])
{
diss[e[i].go]=diss[now]+e[i].c;
q.push(make_pair(diss[e[i].go],e[i].go));
}
}
}
int u[M],v[M],w[M],pos[M],c;
void solve(int l, int r)
{
clear();
ss=n+;
tt=n+;
init(ss,tt);
for(int i = ; i <= m; i++) build(u[i], v[i], );
for(int i = l; i <= r; i++) build(pos[i], tt, );
build(ss, , r - l + );
why += ask();
//cout << ans <<endl;
}
bool cmp_(int a, int b) {
return diss[a] < diss[b];
}
int main()
{
scanf("%d%d%d", &n, &m, &c);
p=;
for(int i = ; i <= m; i++) scanf("%d%d%d", &u[i], &v[i], &w[i]);
for(int i = ; i <= c; i++) scanf("%d", &pos[i]);
for(int i = ; i <= m; i++) addedge(u[i], v[i], w[i]), addedge(v[i], u[i], w[i]);
dijkstra();
//for (int i=1;i<=n;i++) printf("%d\n",diss[i]);
int tmp = ;
for(int i = ; i <= m; i++) {
if(diss[u[i]] > diss[v[i]]) swap(u[i], v[i]);
if(diss[v[i]] == diss[u[i]] + w[i]) {
++tmp;
swap(u[i], u[tmp]);
swap(v[i], v[tmp]);
swap(w[i], w[tmp]);
}
}
m = tmp;
sort(pos + , pos + c + , cmp_);
for(int i = , j; i <= c; i = j) {
j = i;
while(diss[pos[i]] == diss[pos[j]] && j <= c) j++;
if (diss[pos[i]]==inf) break;
solve(i, j - );
//cout << i << " " << j - 1 <<endl;
}
printf("%d", why);
return ;
}

最新文章

  1. springboot使用之四:错误页面404处理建议
  2. Python numpy函数hstack() vstack() stack() dstack() vsplit() concatenate()
  3. AssetBundle系列——场景资源之打包(一)
  4. 最长公共子串 NYOJ 36
  5. SharePoint 2013 开发——开发并部署第一个APP
  6. jsp中的forward和redirect的区别
  7. ubuntu12.04安装jdk-7u79-linux-i586.tar.gz
  8. USB联机线编程接口(API)
  9. 最简单的epoll的使用范例 : 监听 标准输入 ,并将数据回显到终端
  10. Percona 5.7.13 已经发布
  11. 偶现bug如何处理?
  12. add web server(nginx+apache)
  13. vue编程式导航
  14. app优化篇
  15. Linux学习--- 宏定义下#、##的使用
  16. OCM_第九天课程:Section4&mdash;》OCM课程环境搭建
  17. YII2中分页组件的使用
  18. Linux学习笔记之如何让普通用户获得ROOT权限
  19. 日期获取 net
  20. SQL导入的方法,网上看到的

热门文章

  1. 通过docker-composer启动容器nginx,并完成spring.boot的web站点端口转发
  2. Python学习-比较运算符和逻辑运算符
  3. PHP 计数排序
  4. 关于vuex自己理解的三幅图
  5. 戏说云计算之PaaS,IaaS,SaaS
  6. 九度oj 题目1089:数字反转
  7. 总结for循环及for循环增强遍历数组,list,set和map
  8. POJ——T3417 Network
  9. Problem 2669
  10. POJ 1475 推箱