# Tag-网络流

Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

## 代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e4+5;
int T;
typedef long long ll;
const ll INF = 1e15;
struct Flow{
struct edge{
int to,next;
ll cap;
}e[maxn<<2];
int h[maxn];
int cur[maxn];
int cnt;
void init(){
cnt = 0;
memset(h,-1,sizeof(h));

2019-07-15 17:15:53 |  0 Comments  |  网络流

## 代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 205;
struct edge{
int to,next,cap;
}e[maxn*maxn * 16];
int cnt = 0;
int h[maxn*maxn];
e[cnt].to = v;e[cnt].cap = c;e[cnt].next = h[u];
h[u] = cnt++;
return;
}
int d[maxn*maxn];
const int INF = 1e9;
bool BFS(int s,int t){
for(int i = s;i <= t;++i){
d[i] = INF;
}
d[s] = 0;
queue<int>q;


## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num << 3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
int n,m;
const int maxn = 2e5+25;
const int max

## 题目描述

（1）计算其最长不下降子序列的长度s。

（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。

（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。

## 样例输入

4
3 6 2 5

2
2
3

## 代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c

## 代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
int S,T;
const int maxn = 55;
const int maxm = 1005;
const int INF = 1e9;
struct Flow{
int h[maxn],cur[maxn];
struct edge{
int to,next,cap;
}e[maxm<<1];
int cnt;
e[cnt].to = v;e[cnt].next = h[u];e[cnt].cap = c;
h[u] = cnt++;
return;
}
int d[maxn];
bool BFS(int s,int t){
queue<int>q;
for(int i = s;i <= t;++i){
d[i] = INF;
}
d[s] = 0;
q.push(s);
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = h[now];i != -1;i = e[i].next){
int v = e[i].t

## 题解：

Kruskal算法是一种贪心算法，每次选择边权最小的一条边，检测一下两个端点是否都在一个并查集里，如果不是就加上这一条边，代表最小生成树选择这一条边。

## 代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2e4+5;
const int maxm = 2e5+5;
struct edge{
int fr,to,next,cap;
}e[maxm<<3];
int cnt = 0;
int h[maxn];
int cur[maxn],d[maxn];
const int INF = 1e9;
struct edge2{
int fr,to,dis;
}e2[maxm];
int n,m;
/*
bool cmp(edge2 a,edge2 b){
return a.dis < b.dis;
}//其实不用排序
*/
e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = c;
e[cnt].next = h[u];h[u] = cnt++;
e[cnt].fr = v;e[cnt].to = u;e[cnt].cap 

## Description

MZL is an active girl who has her own country.

Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broken.She also remebered that exactly one of the following things happened every recent M years:

1.She rebuild some cities that are connected with X directly and indirectly.Notice that if a city was rebuilt that it will never be broken again.

2.There is a bidirectional road between city X and city Y built.

3.There is a earthquake happened and some roads were destroyed.

She forgot the exactly cities that were rebuilt,but she only knew that no more than K cities were rebuilt in one year.Now she only want to know the maximal number of cities that could be rebuilt.At the same time she want you to tell her the smallest lexicographically plan under the best answer.Notice that 8 2 1 is smaller than 10 0 1.

## Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb

## Sample Input

6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6

## Sample Output

8

【样例说明】 边(4,6)的权由7修改为3，代价为4

## HINT

1<=n<=50,1<=m<=800,1<=wi<=1000
n-->点数..m-->边数..wi--->边权

## 题解

widiwj+djwi−di≤wj+dj

wiwjdi+djwi−wj≤di+dj

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5+5,INF=1e9;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c ==

## 题目描述

### 样例输入

3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0﻿​

### 样例输出

25﻿​

### 题解

#### 网络流建图方式：

score小于零的：从此点向汇点T连边，流量为-score

### 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == '
Title - Artist
0:00