# Tag-费用流

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

## 代码

#include <bits/stdc++.h>
using namespace std;
int T,S,E;
const int maxn = 205;
const int INF = 2e9;
struct edge{
int fr,to,next,cap,dis;
}e[maxn<<3];
int h[maxn];
int cnt = 0;
void add(int u,int v,int cap,int d){
e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = cap;e[cnt].dis = d;e[cnt].next = h[u];h[u] = cnt++;
e[cnt].fr

#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int INF = 1e9;
typedef long long ll;
ll a[maxn],b[maxn],c[maxn];
int p[maxn];
int d[maxn<<1],vis[maxn<<1];
deque<int>q;
int n;
struct edge{
int to,next,cap,cost;
}e[maxn*maxn*2];
int S,T;
int h[maxn<<1];
int cnt = 0;
void add(int u,int v,int cap,int cost){
e[cnt].to = v;e[cnt].cap = cap;e[cnt].cost = cost;
e[cnt].next = h[u];h[u] = cnt++;
return;
}
bool spfa(int s,int t){
for(int i = s;i <= t;++i){
d[i] = -INF;
vis[i] = 0;
}
d[t] = 0;
vis[t] = 1;
q.push_back(t);
while(!q.empty()){
int now = q.front();
q.pop_front();
vis[now] = 0;
for(int i = h[now];i != -1;i = e[i].next){
int v = e[i].to;
if(e[i^1].cap && d[v] < d[now] - e[i].cost){
d[v] = d[now] - e[i].cost;
if(!vis[v]){
vis[v] = 1;
if(!q.empty() && d[q.front()] < d[v])q.push_front

## 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.

## 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--->边权

## 题解

#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
Title - Artist
0:00