#include <cstdio>
const int MAX_NODE = 110, MAX_EDGE = 10010 * 2, INF = 1e9;
typedef int arrayN[MAX_NODE];
typedef int arrayE[MAX_EDGE];
int min(int a, int b) { return a < b ? a : b; }
arrayE edgeCost, edgeFlow, toNode, nextEdge;
arrayN cur, num, dis, pre, queue, head;
int n, qhead, tail;
void addEdge(int u, int v, int w)
{
static int tot = 1;
edgeCost[++tot] = w;
edgeFlow[tot] = 0;
toNode[tot] = v;
nextEdge[tot] = head[u];
head[u] = tot;
}
int ar(int s, int t) //确认流
{
int flow = INF, p;
for (p = t; p != s; p = toNode[pre[p] ^ 1])
flow = min(flow, edgeCost[pre[p]] - edgeFlow[pre[p]]);
for (p = t; p != s; p = toNode[pre[p] ^ 1])
edgeFlow[pre[p]] += flow, edgeFlow[pre[p] ^ 1] -= flow;
return flow;
}
void bfs(int s) //拓扑
{
int now, p;
queue[tail++] = s;
dis[s] = 0;
while (qhead < tail)
{
now = queue[qhead++];
for (p = head[now]; p; p = nextEdge[p])
if (toNode[p] != s && !dis[toNode[p]])
dis[toNode[p]] = dis[now] + 1, queue[tail++] = toNode[p];
}
}
int MAXflow(int s, int t)
{
bool ok;
int ans = 0, x = s, m, p, i;
bfs(t); //对网络进行拓扑
for (i = 1; i <= n; i++)
num[dis[i]]++;
for (i = 1; i <= n; i++)
cur[i] = head[i];
while (dis[s] < n)
{
ok = false;
if (x == t) //到达目的地,更新流信息
ans += ar(s, t), x = s;
for (p = cur[x]; p; p = nextEdge[p])
if (edgeCost[p] > edgeFlow[p] && dis[x] == dis[toNode[p]] + 1)
{
ok = true, cur[x] = p, pre[toNode[p]] = p, x = toNode[p];
break;
}
if (!ok) //不可以流则回退
{
m = n;
for (p = head[x]; p; p = nextEdge[p])
if (edgeCost[p] > edgeFlow[p])
m = min(m, dis[toNode[p]]);
if (--num[dis[x]] == 0)
break;
num[dis[x] = m + 1]++;
cur[x] = head[x];
if (x != s)
x = toNode[pre[x] ^ 1];
}
}
return ans;
}
int main()
{
int m, u, v, w;
scanf("%d %d", &n, &m); //n节点,m边
for (int i = 0; i < m; ++i)
{
scanf("%d %d %d", &u, &v, &w); //u,v间有可以通过w流量的边
addEdge(u, v, w); //正向边流量w
addEdge(v, u, 0); //空的反向边
addEdge(v, u, w);
addEdge(u, v, 0);
}
printf("Max flow from Node 1 to Node n:%d", MAXflow(1, n));
return 0;
}
eiclpy 发布的帖子
-
网络最大流量算法
-
RE: 快速傅里叶变换实现两个超大整数(100000位)乘法
测试
import random import os for _ in range(10): with open('input.txt', 'w') as f: val1 = random.randint(9*10**10000, 10**100000) val2 = random.randint(9*10**10000, 10**100000) print(val1, file=f) print(val2, file=f) os.system(r'.\fft.exe < input.txt > out.txt') with open('out.txt', 'r') as f1: if f1.read().strip() == str(val1*val2): print('OK') else: print("Wrong")
-
快速傅里叶变换实现两个超大整数(100000位)乘法
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int SIZEN = 800010, BASE = 10; const double PI = acos(-1), eps = 1e-6; class Complex { //复数 public: double real, imag; Complex(double x = 0, double y = 0) { real = x, imag = y; } }; Complex operator+(Complex a, Complex b) { return Complex(a.real + b.real, a.imag + b.imag); } Complex operator-(Complex a, Complex b) { return Complex(a.real - b.real, a.imag - b.imag); } Complex operator*(Complex a, Complex b) { return Complex(a.real * b.real - a.imag * b.imag, a.real * b.imag + b.real * a.imag); } Complex operator/(Complex a, double b) { return Complex(a.real / b, a.imag / b); } class Poly { public: int n; //n-1次多项式,有n个系数 Complex s[SIZEN]; void Initialize(char str[]) { n = strlen(str); for (int i = 0; i < n; i++) s[i] = Complex(str[n - 1 - i] - '0', 0); } void Assign(char str[]) { static int a[SIZEN]; int len; for (int i = 0; i < n; i++) a[i] = int(s[i].real + 0.5); for (len = 0; len < n || a[len]; len++) { a[len + 1] += a[len] / BASE; a[len] %= BASE; } while (len > 1 && !a[len - 1]) len--; for (int i = 0; i < len; i++) str[i] = a[len - 1 - i] + '0'; str[len] = 0; } void Print(void) { static char str[SIZEN]; Assign(str); printf("%s\n", str); } void Rader_Transform(void) { int j = 0, k; for (int i = 0; i < n; i++) { if (j > i) swap(s[i], s[j]); k = n; //进位 while (j & (k >>= 1)) j &= ~k; j |= k; } } void FFT(bool type) { //type=1是DFT求值(系数求点),type=0是IDFT插值(点求系数) Rader_Transform(); //重新排列数组 double pi = type ? PI : -PI; //IDFT的要点1:π变负 Complex w0; for (int step = 1; step < n; step <<= 1) { //在这层循环中我们把相邻两个长度为step的点值表达式合并 for (int H = 0; H < n; H += step << 1) { //将[H,H+step)和[H+step,H+2*step)这两个点值表达式合为一个 double alpha = pi / step; //2*step次单位根,转动的角度为alpha的倍数 Complex wn(cos(alpha), sin(alpha)), wk(1.0, 0.0); //wn是幅角为alpha的单位根,wk从1开始每次乘以wn就能遍历每个2*step次单位根 for (int k = 0; k < step; k++) { //执行一次旋转操作 int Ek = H + k, Ok = H + k + step; //旋转操作的第一项和第二项 Complex t = wk * s[Ok]; //旋转因子 s[Ok] = s[Ek] - t; s[Ek] = s[Ek] + t; wk = wk * wn; } } } if (!type) for (int i = 0; i < n; i++) s[i] = s[i] / n; //IDFT的要点2:除以n } void operator*=(Poly &b) { int S = 1; while (S < n + b.n) S <<= 1; n = b.n = S; FFT(true); b.FFT(true); for (int i = 0; i < n; i++) s[i] = s[i] * b.s[i]; FFT(false); } }; Poly A, B; int main() { char str[SIZEN]; scanf("%s", str); A.Initialize(str); scanf("%s", str); B.Initialize(str); A *= B; A.Print(); return 0; }
-
RE: 网络最短路算法实现(单源/全源)
全源最短路
//Floyd全源最短路 #include<stdio.h> int a[100][100]; int main(){ int n,m; scanf("%d%d",&n,&m);//共n个点,m条边 for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]=100000007; for(int i=0;i<m;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w);//编号u,编号v点间有一条长度ww的路 a[u][v]=a[v][u]=w; } for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j]; for(int i=1;i<n;++i) for(int j=i+1;j<=n;++j) printf("%d-->%d: %d\n",i,j,a[i][j]); return 0; }
-
RE: 求已知网络中关键节点,关键线路
将已知网络关键线路即桥定义为:删除此线路后,存在原网络中联通的节点,在新的网络中不连通
#include <cstdio> #include <map> #include <vector> #include <algorithm> using namespace std; int head[1000], to[100000], nxt[100000]; void addEdge(int u, int v) { static int tot = 1; to[++tot] = v; nxt[tot] = head[u]; head[u] = tot; to[++tot] = u; nxt[tot] = head[v]; head[v] = tot; } int min(int a, int b) { return a < b ? a : b; } int dfn[1000], low[1000]; vector<pair<int, int>> br; void tarjan(int s, int f) { static int index; int cnt = 0; dfn[s] = low[s] = ++index; for (int p = head[s]; p; p = nxt[p]) if (!dfn[to[p]]) { tarjan(to[p], s); low[s] = min(low[s], low[to[p]]); if (low[to[p]] > dfn[s]) br.push_back(s < to[p] ? make_pair(s, to[p]) : make_pair(to[p], s)); } else if (to[p] != f) low[s] = min(low[s], dfn[to[p]]); } int main() { int n, m; scanf("%d%d", &n, &m); //n节点m条连接(节点编号1-n) for (int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); addEdge(u, v); //编号u,v的节点连接 } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0); sort(br.begin(), br.end()); for (int i = 0; i < br.size(); ++i) printf("Bridge between Node %d and Node %d\n", br[i].first, br[i].second); return 0; }
-
求已知网络中关键节点,关键线路
将已知网络关键节点即割点定义为:删除此节点后,存在原网络中联通的节点,在新的网络中不连通
#include <cstdio> int head[1000], to[100000], next[100000]; void addEdge(int u, int v) { static int tot = 1; to[++tot] = v; next[tot] = head[u]; head[u] = tot; to[++tot] = u; next[tot] = head[v]; head[v] = tot; } int min(int a, int b) { return a < b ? a : b; } int dfn[1000], low[1000]; bool bcut[1000]; void tarjan(int s, int f) { static int index; int cnt = 0; dfn[s] = low[s] = ++index; for (int p = head[s]; p; p = next[p]) if (!dfn[to[p]]) { tarjan(to[p], s); low[s] = min(low[s], low[to[p]]); ++cnt; if (low[to[p]] >= dfn[s] && f) bcut[s] = true; } else low[s] = min(low[s], dfn[to[p]]); if (f && cnt > 1) bcut[s] = true; } int main() { int n, m; scanf("%d %d", &n, &m); //n节点m条连接(节点编号1-n) for (int i = 0; i < m; ++i) { int u, v; scanf("%d %d", &u, &v); addEdge(u, v); //编号u,v的节点连接 } for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i, 0); } for (int i = 1; i <= n; ++i) { printf("Node %d: dfn:%d low:%d iscut:%d\n", i, dfn[i], low[i], bcut[i]); } return 0; }