3931: [CQOI2015]网络吞吐量
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://www.lydsy.com/JudgeOnline/problem.php?id=3931
Description
路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1和n直接相连的链路。
Input
输入文件第一行包含两个空格分开的正整数n和m，分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。接下来m行，每行包含三个空格分开的正整数a、b和d，表示从路由器a到路由器b存在一条距离为d的双向链路。 接下来n行，每行包含一个正整数c，分别给出每一个路由器的吞吐量。
Output
输出一个整数，为题目所求吞吐量。
Sample Input
7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1
Sample Output
70
HINT
对于100%的数据，n≤500，m≤100000，d,c≤10^9
题意
题解：
跑最短路之后拆点，拆点来维护每个点最大扔出去的网络吞吐量
然后直接搞就好了……
这道题要爆int = =！
怒wa一发
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 110000
#define mod 10007
#define eps 1e-9
int Num;
//const int inf=0x7fffffff; //§ß§é§à§é¨f§³
const ll Inf=0x3f3f3f3f3f3f3f3fll;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//**************************************************************************************
namespace NetFlow
{
const ll MAXN=,MAXM=,inf=0x3f3f3f3f3f3f3f3fll;
struct Edge
{
ll v,c,f,nx;
Edge() {}
Edge(ll v,ll c,ll f,ll nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
ll G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
void init(ll _n)
{
N=_n,sz=; memset(G,-,sizeof(G[])*N);
}
void link(ll u,ll v,ll c)
{
E[sz]=Edge(v,c,,G[u]); G[u]=sz++;
E[sz]=Edge(u,,,G[v]); G[v]=sz++;
}
bool bfs(int S,int T)
{
static int Q[MAXN]; memset(dis,-,sizeof(dis[])*N);
dis[S]=; Q[]=S;
for (int h=,t=,u,v,it;h<t;++h)
{
for (u=Q[h],it=G[u];~it;it=E[it].nx)
{
if (dis[v=E[it].v]==-&&E[it].c>E[it].f)
{
dis[v]=dis[u]+; Q[t++]=v;
}
}
}
return dis[T]!=-;
}
ll dfs(ll u,ll T,ll low)
{
if (u==T) return low;
ll ret=,tmp,v;
for (ll &it=cur[u];~it&&ret<low;it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+&&E[it].c>E[it].f)
{
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
{
ret+=tmp; E[it].f+=tmp; E[it^].f-=tmp;
}
}
}
if (!ret) dis[u]=-; return ret;
}
ll dinic(int S,int T)
{
ll maxflow=,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G[])*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
}
using namespace NetFlow; int n,m;
struct node
{
ll x,y;
};
vector<node> EE[maxn];
ll d[maxn];
ll inq[maxn];
ll cost[maxn];
struct EEdge
{
ll x,y,z;
};
EEdge edge[maxn];
vector<ll> U,V;
int main()
{
n=read(),m=read();
for(int i=;i<=m;i++)
{
edge[i].x=read(),edge[i].y=read(),edge[i].z=read();
EE[edge[i].x].push_back((node){edge[i].y,edge[i].z});
EE[edge[i].y].push_back((node){edge[i].x,edge[i].z});
}
for(int i=;i<=n;i++)
d[i]=Inf;
queue<int> Q;
Q.push();
d[]=;
inq[]=;
while(!Q.empty())
{
int u = Q.front();
Q.pop();
inq[u]=;
for(int i=;i<EE[u].size();i++)
{
node v = EE[u][i];
if(v.y+d[u]<d[v.x])
{
d[v.x]=v.y+d[u];
if(!inq[v.x])
{
Q.push(v.x);
inq[v.x]=;
}
}
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<EE[i].size();j++)
{
node v = EE[i][j];
if(d[i]+v.y==d[v.x])
U.push_back(i+n),V.push_back(v.x);
}
}
init();
for(int i=;i<=n;i++)
{
cost[i]=read();
if(i!=&&i!=n)
link(i,i+n,cost[i]);
else
link(i,i+n,inf);
}
for(int i=;i<V.size();i++)
link(U[i],V[i],inf);
printf("%lld\n",dinic(,*n));
}