[CQOI2015]网络吞吐量
题目背景
路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法 OSPF (开放式最短路径优先) 中，路由器会使用经典的 Dijkstra 算法计算最短路径，然后尽量沿最短路径转发数据包。
题目描述
现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），网络中的路由器使用 到 编号，假设所有数据包一定沿最短路径转发，试计算从路由器 到路由器 的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器 到路由器 作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将 和 直接相连的链路。
输入格式
输入的第一行是用空格隔开的两个整数，分别代表路由器的数量 和链路的数量 。
第 到第 行，每行三个整数 ，代表存在一条连结路由器 和路由器 的距离为 的双向链路。
第 到第 行，每行一个整数，第 行的整数代表路由器 的吞吐量 。
输出格式
输出一行一个整数，代表网络的最大吞吐量。
样例 #1
样例输入 #1
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
样例输出 #1
70
提示
数据规模与约定
对于 的数据，保证 ，，。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define IOS ios_base ::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define int ll
#define re register
const ll INF = 1e18;
int n, m;
const int N = 509, M = 1e5 + 9;
int a[N];
vector<int> to[N];
vector<int> val[N];
ll dist[N], deep[N * 2];
bool st[N];
int numE, head[N * 2];
struct E {
int next, to, w;
} e[M << 2];
void add(int a, int b, int c) {
e[numE] = {head[a], b, c};
head[a] = numE++;
e[numE] = {head[b], a, 0};
head[b] = numE++;
}
void SPFA() {
queue<int> qu;
memset(dist, 0x3f, sizeof dist);
qu.push(1);
dist[1] = 0;
st[1] = true;
while (!qu.empty()) {
int t = qu.front();
qu.pop();
st[t] = false;
for (re int i = 0; i < to[t].size(); i++) {
int v = to[t][i];
if (dist[v] > dist[t] + val[t][i]) {
dist[v] = dist[t] + val[t][i];
if (!st[v]) {
st[v] = true;
qu.push(v);
}
}
}
}
}
int dinic(int x, int t, int flow) {
if (x == t)
return flow;
int sum = 0;
for (int i = head[x]; ~i; i = e[i].next) {
int v = e[i].to;
if (e[i].w != 0 && (deep[v] == deep[x] + 1)) {
int temp = dinic(v, t, min(flow - sum, e[i].w));
e[i].w -= temp;
e[i ^ 1].w += temp;
sum += temp;
if (sum == flow)
return sum;
}
}
return sum;
}
bool make_level(int s, int t) {
memset(deep, 0, sizeof deep);
queue<int> qu;
deep[s] = 1;
qu.push(s);
while (!qu.empty()) {
int x = qu.front();
qu.pop();
if (x == t)
return true;
for (int i = head[x]; ~i; i = e[i].next) {
int v = e[i].to;
if (deep[v] == 0 && e[i].w != 0) {
qu.push(v);
deep[v] = deep[x] + 1;
}
}
}
return false;
}
int Max_flow(int s, int t) {
int ans = 0;
while (make_level(s, t))
ans += dinic(s, t, INF);
return ans;
}
signed main() {
IOS;
memset(head, -1, sizeof head);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
to[a].push_back(b);
to[b].push_back(a);
val[a].push_back(c);
val[b].push_back(c);
}
for (int i = 1; i <= n; i++)
cin >> a[i];
SPFA();
for (re int i = 1; i <= n; i++) {
for (re int j = 0; j < to[i].size(); j++) {
int go = to[i][j];
int vaL = val[i][j];
if (dist[go] == dist[i] + vaL) {
add(i + n, go, INF);
}
}
}
add(2 * n + 1, 1, INF);
add(2 * n, 2 * n + 2, INF);
a[1] = INF, a[n] = INF;
for (int i = 1; i <= n; i++)
add(i, i + n, a[i]);
cout << Max_flow(2 * n + 1, 2 * n + 2) << '\n';
return 0;
}
飞行员配对方案问题
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 9;
int n, m;
int head[N], numE, match[N],deep[N];
const int INF = 0x3f3f3f3f;
bool st[N];
struct E
{
int next, to, w;
} e[N];
void add(int a, int b,int c)
{
e[numE] = {head[a], b, c};
head[a] = numE++;
e[numE] = {head[b],a,0};
head[b] = numE++;
}
int dinic(int x,int t,int flow)
{
if(x == t) return flow;
int sum = 0;
for(int i=head[x]; ~i; i=e[i].next)
{
int v = e[i].to;
if(e[i].w != 0 && (deep[v] == deep[x] + 1))
{
int temp = dinic(v,t,min(flow - sum,e[i].w));
e[i].w -= temp;
e[i ^ 1].w += temp;
sum += temp;
if(sum == flow) return sum;
}
}
return sum;
}
bool make_level(int s,int t)
{
memset(deep,0,sizeof deep);
int qu[1009];
memset(qu,0,sizeof qu);
deep[s] = 1;
int hh = 1,tt = 0;
qu[++tt] = s;
while(hh <= tt)
{
int x = qu[hh++];
if(x == t) return true;
for(int i=head[x]; ~i; i=e[i].next)
{
int v = e[i].to;
if(deep[v] == 0 && e[i].w != 0)
{
qu[++tt] = v;
deep[v] = deep[x] + 1;
}
}
}
return false;
}
int Maxflow(int s,int t)
{
int ans = 0;
while(make_level(s,t))
{
ans += dinic(s,t,INF);
}
return ans;
}
int main()
{
memset(head, -1, sizeof head);
cin >> n >> m;
int a, b;
int S = 2 * n + 1,T = 2 * n + 2;
for(int i=1; i<=m; i++) add(S,i,1);
for(int i=m+1; i<=n; i++) add(i,T,1);
while (~scanf("%d%d", &a, &b))
{
add(a,b,1);
}
cout << Maxflow(S,T) << "\n";
return 0;
}
https://ac.nowcoder.com/acm/contest/36913/1005
sap跑最大流
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int N = 29;
int h[N][N],num[N][N],a[509][2];
int r,c,d,n;
int cnt[1009],dep[1009];
int head[1009],numE;
struct E
{
int next,to,w;
}e[2000010];
void add(int a,int b,int c)
{
e[numE] = {head[a],b,c};
head[a] = numE++;
e[numE] = {head[b],a,0};
head[b] = numE++;
}
int dfs(int x, int t, int flow)
{
if (x == t) return flow;
int sum = 0;
for(int i = head[x]; i != -1; i = e[i].next)
{
int y = e[i].to;
if (e[i].w == 0) continue;
if (dep[x] == dep[y] + 1)
{
int tmp = dfs(y, t, min(e[i].w, flow - sum));
e[i].w -= tmp;
e[i^1].w += tmp;
sum += tmp;
if (sum == flow) return sum;
}
}
if (dep[2*n+1] >= t) return sum; //执行flag
cnt[dep[x]]--;
if (cnt[dep[x]] == 0) dep[2*n+1] = 2*n+2; // flag 变量
dep[x]++;
cnt[dep[x]]++;
return sum;
}
int Maxflow(int s,int t)
{
int ans = 0;
while(dep[s] < t)
{
ans += dfs(s,t,INF);
}
return ans;
}
int cal(int x1,int y1,int x2,int y2)
{
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int main()
{
memset(head,-1,sizeof head);
cin >> r >> c >> d;
for(int i=1; i<=r; i++)
{
for(int j=1; j<=c; j++)
{
scanf("%1d",&h[i][j]);
if(h[i][j] != 0)
{
++n;
num[i][j] = n;
a[n][0] = i;
a[n][1] = j;
}
}
}
int sum = 0;
for(int i=1; i<=r; i++)
{
for(int j=1; j<=c; j++)
{
char ch;
scanf(" %c",&ch);
if(h[i][j] != 0)
{
int x,y;
x = num[i][j],y = num[i][j] + n;
add(x,y,h[i][j]);
if(i <= d || j <= d || i + d > r || j + d > c)
{
int x = num[i][j] + n;
int y = n*2 + 2;
add(x,y,INF);
}
}
if(ch == 'L')
{
int x = 2 * n + 1;
int y = num[i][j];
add(x,y,1);
sum++;
}
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
int xi = a[i][0];
int yi = a[i][1];
int xj = a[j][0];
int yj = a[j][1];
if(cal(xi,yi,xj,yj) <= d * d)
{
add(num[a[i][0]][a[i][1]]+n, num[a[j][0]][a[j][1]], INF);
add(num[a[j][0]][a[j][1]]+n, num[a[i][0]][a[i][1]], INF);
}
}
}
cnt[0] = 2*n + 2;
cout<< sum - Maxflow(2 * n + 1,2 * n + 2) <<"\n";
return 0;
}
dinic 邻接表跑最大流
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int N = 29;
int h[N][N],num[N][N],a[509][2];
int r,c,d,n;
int cnt[1009],deep[1009];
int head[1009],numE;
struct E
{
int next,to,w;
}e[2000010];
void add(int a,int b,int c)
{
e[numE] = {head[a],b,c};
head[a] = numE++;
e[numE] = {head[b],a,0};
head[b] = numE++;
}
int dfs(int x,int t,int flow)
{
if(x == t) return flow;
int sum = 0;
for(int i=head[x]; ~i; i=e[i].next)
{
int v = e[i].to;
if(e[i].w != 0 && (deep[v] == deep[x] + 1))
{
int temp = dfs(v,t,min(flow - sum,e[i].w));
e[i].w -= temp;
e[i ^ 1].w += temp;
sum += temp;
if(sum == flow) return sum;
}
}
return sum;
}
bool make_level(int s,int t)
{
memset(deep,0,sizeof deep);
int qu[1009];
memset(qu,0,sizeof qu);
deep[s] = 1;
int hh = 1,tt = 0;
qu[++tt] = s;
while(hh <= tt)
{
int x = qu[hh++];
if(x == t) return true;
for(int i=head[x]; ~i; i=e[i].next)
{
int v = e[i].to;
if(deep[v] == 0 && e[i].w != 0)
{
qu[++tt] = v;
deep[v] = deep[x] + 1;
}
}
}
return false;
}
int Maxflow(int s,int t)
{
int ans = 0;
while(make_level(s,t))
{
ans += dfs(s,t,INF);
}
return ans;
}
int cal(int x1,int y1,int x2,int y2)
{
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int main()
{
memset(head,-1,sizeof head);
cin >> r >> c >> d;
for(int i=1; i<=r; i++)
{
for(int j=1; j<=c; j++)
{
scanf("%1d",&h[i][j]);
if(h[i][j] != 0)
{
++n;
num[i][j] = n;
a[n][0] = i;
a[n][1] = j;
}
}
}
int sum = 0;
for(int i=1; i<=r; i++)
{
for(int j=1; j<=c; j++)
{
char ch;
scanf(" %c",&ch);
if(h[i][j] != 0)
{
int x,y;
x = num[i][j],y = num[i][j] + n;
add(x,y,h[i][j]);
if(i <= d || j <= d || i + d > r || j + d > c)
{
int x = num[i][j] + n;
int y = n*2 + 2;
add(x,y,INF);
}
}
if(ch == 'L')
{
int x = 2 * n + 1;
int y = num[i][j];
add(x,y,1);
sum++;
}
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
int xi = a[i][0];
int yi = a[i][1];
int xj = a[j][0];
int yj = a[j][1];
if(cal(xi,yi,xj,yj) <= d * d)
{
add(num[a[i][0]][a[i][1]]+n, num[a[j][0]][a[j][1]], INF);
add(num[a[j][0]][a[j][1]]+n, num[a[i][0]][a[i][1]], INF);
}
}
}
cnt[0] = 2*n + 2;
cout<< sum - Maxflow(2 * n + 1,2 * n + 2) <<"\n";
return 0;
}
京公网安备 11010502036488号