Dinic板子：
const int tmax=1e4+5,inf_int=1e9+5;
struct edge{
int to,cap,rev;
};
vector<edge> G[tmax];
int level[tmax];
int iter[tmax];
void addedge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty())
{
int v=que.front();
que.pop();
for(int i=0;i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int Dinic(int s,int t)
{
int flow=0;
while(1)
{
bfs(s);
if(level[t]<0) return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,inf_int))>0)
flow+=f;
}
}
View Code
Dijkstra+Heap板子：
const int tmax=1e4+5,inf_int=1e9+5;
ll dis1[tmax], dis2[tmax];
struct node
{
ll d;
int x;
bool operator<(const node &b)const
{
return d>b.d;
}
};
vector<Pii> GG[tmax];
priority_queue<node> Q;
bool vis[tmax];
void dijk(int s,ll *d)
{
int i,u,v,w,len;
node tmp;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++) d[i]=inf;
d[s]=0;
Q.push((node){0,s});
while(!Q.empty())
{
tmp=Q.top();
Q.pop();
u=tmp.x;
if(vis[u]) continue;
vis[u]=true;
len=GG[u].size();
for(i=0;i<len;i++)
{
v=GG[u][i].first;
w=GG[u][i].second;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
Q.push((node){d[v],v});
}
}
}
return;
}
View Code
HDU 3416
题意：给出一个图，有多少个边不重复的最短路。
题解：先跑最短路，找出从start到end的所有最短路，先跑正向在跑反向，如果dis1[u]+cost[i]+dist2[v]==dis1[n]，即可判断该边是否在最短路上。
把最短上的边构图（cap=1）跑最大流即可.
#include <bits/stdc++.h>
#define Pii pair<int,int>
using namespace std;
typedef long long ll;
const ll inf=1e16;
const int tmax=2e5+5,inf_int=1e9+5;
int n, m, u[tmax], v[tmax], c[tmax];
ll dis1[tmax], dis2[tmax];
struct node
{
ll d;
int x;
bool operator<(const node &b)const
{
return d>b.d;
}
};
vector<Pii> GG[tmax];
priority_queue<node> Q;
bool vis[tmax];
void Dijk(int s,ll *d)
{
int i,u,v,w,len;
node tmp;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++) d[i]=inf;
d[s]=0;
Q.push((node){0,s});
while(!Q.empty())
{
tmp=Q.top();
Q.pop();
u=tmp.x;
if(vis[u]) continue;
vis[u]=true;
len=GG[u].size();
for(i=0;i<len;i++)
{
v=GG[u][i].first;
w=GG[u][i].second;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
Q.push((node){d[v],v});
}
}
}
return;
}
struct edge{
int to,cap,rev;
};
vector<edge> G[tmax];
int level[tmax];
int iter[tmax];
void addedge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty())
{
int v=que.front();
que.pop();
for(int i=0;i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int Dinic(int s,int t)
{
int flow=0;
while(1)
{
bfs(s);
if(level[t]<0) return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,inf_int))>0)
flow+=f;
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
for(cin>>T; T--; )
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>u[i]>>v[i]>>c[i];
GG[u[i]].push_back(Pii(v[i],c[i]));
}
int A, B;
cin>>A>>B;
Dijk(A, dis1);
for(int i=1; i<=n; i++)
GG[i].clear();
for(int i=1; i<=m; i++)
GG[v[i]].push_back(Pii(u[i],c[i]));
Dijk(B, dis2);
for(int i=1; i<=m; i++)
{
if(dis1[u[i]]+c[i]+dis2[v[i]]==dis1[B])
addedge(u[i],v[i],1);
}
cout<<Dinic(A,B)<<endl;
for(int i=1; i<=n; i++)
{
G[i].clear(); GG[i].clear();
}
}
return 0;
}
View Code
HDU 6532
题意：给出一个图，求至少删除多少边权后能够最短路长度增加（删除后不联通可以）
题解：以最短路上的边构图，跑一下最小割即可。
#include <bits/stdc++.h>
#define Pii pair<int,int>
using namespace std;
typedef long long ll;
const ll inf=1e16;
const int tmax=1e4+5,inf_int=1e9+5;
int n, m, u[tmax], v[tmax], c[tmax];
ll dis1[tmax], dis2[tmax];
struct node
{
ll d;
int x;
bool operator<(const node &b)const
{
return d>b.d;
}
};
vector<Pii> GG[tmax];
priority_queue<node> Q;
bool vis[tmax];
void Dijk(int s,ll *d)
{
int i,u,v,w,len;
node tmp;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++) d[i]=inf;
d[s]=0;
Q.push((node){0,s});
while(!Q.empty())
{
tmp=Q.top();
Q.pop();
u=tmp.x;
if(vis[u]) continue;
vis[u]=true;
len=GG[u].size();
for(i=0;i<len;i++)
{
v=GG[u][i].first;
w=GG[u][i].second;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
Q.push((node){d[v],v});
}
}
}
return;
}
struct edge{
int to,cap,rev;
};
vector<edge> G[tmax];
int level[tmax];
int iter[tmax];
void addedge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty())
{
int v=que.front();
que.pop();
for(int i=0;i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int Dinic(int s,int t)
{
int flow=0;
while(1)
{
bfs(s);
if(level[t]<0) return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,inf_int))>0)
flow+=f;
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
for(cin>>T; T--; )
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>u[i]>>v[i]>>c[i];
GG[u[i]].push_back(Pii(v[i], c[i]));
}
Dijk(1, dis1);
for(int i=1; i<=n; i++)
GG[i].clear();
for(int i=1; i<=m; i++)
GG[v[i]].push_back(Pii(u[i],c[i]));
Dijk(n,dis2);
for(int i=1; i<=m; i++)
{
if(dis1[u[i]]+c[i]+dis2[v[i]]==dis1[n])
addedge(u[i],v[i],c[i]);
}
cout<<Dinic(1,n)<<endl;
for(int i=1; i<=n; i++)
{
G[i].clear(); GG[i].clear();
}
}
return 0;
}
View Code