Tag: 费用流

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1221

真·双倍经验

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000;
const int INF = 100000000;
 
int head[N],nxt[N],to[N],cost[N],flow[N],dis[N],inq[N];
int n,st,sc,ft,fc,arr[N],S,T,p,sur[N],FLOW[N]; 
queue<int> que;
  
inline int read(){
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
#define id(x,ty) ((x)*2+ty)
inline void Add_Edge(int u, int v, int f, int c) {
    static int TT = 1;
    to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
    to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}
 
inline int SPFA() {
    memset(dis,127,sizeof(dis));
    memset(FLOW,0,sizeof(FLOW));
    que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
     
    while (!que.empty()) {
        int w = que.front(); que.pop(); inq[w] = 0;
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
            dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
            FLOW[to[i]] = min(FLOW[w], flow[i]);
            if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
        }
    } return FLOW[T];
}
 
inline int MCMF() {
    int ret = 0;
    for (int w=T,f;f=SPFA();w=T) 
        for (int t=sur[w];w!=S;t=sur[w]) 
            flow[t] -= f, 
            flow[t^1] += f,
            ret += cost[t]*f, 
            w = to[t^1];
    return ret;
}
 
int main(){
    n = read(); ft = read()+1; st = read()+1; p = read(); fc = read(); sc = read(); S = 0; T = 1;
    for (int i=1;i<=n;i++) arr[i] = read();
    for (int i=1;i<=n;i++) Add_Edge(S,id(i,0),arr[i],0), Add_Edge(id(i,1),T,arr[i],0);
    for (int i=1;i<n;i++) Add_Edge(id(i,0),id(i+1,0),INF,0);
    for (int i=1;i<=n;i++) if (i + ft <= n) Add_Edge(id(i,0),id(i+ft,1),INF,fc);
    for (int i=1;i<=n;i++) if (i + st <= n) Add_Edge(id(i,0),id(i+st,1),INF,sc);
    for (int i=1;i<=n;i++) Add_Edge(S,id(i,1),INF,p);
    printf("%d\n",MCMF());
    return 0;
}

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=741

虽然是“网络流24题”之一，然而可以O(n)搞
来来来，我们一起来推式子！
6541324587

#include<bits/stdc++.h>
using namespace std;

const int N = 100+9;

int n,arr[N],sum,vout,sta;

inline int read(){
	char c=getchar(); int ret = 0, f = 1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	n = read(); 
	for (int i=1;i<=n;i++) sum += (arr[i] = read()); sum /= n;
	for (int i=1;i<=n;i++) arr[i] -= sum - arr[i-1];
	nth_element(arr+1,arr+n/2,arr+n); sta=arr[n/2];
	for (int i=1;i<=n;i++) vout += abs(arr[i]-sta);
	cout<<vout<<endl;  
	return 0;
} 

感觉真的是好神奇啊！

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=461

建图方法是：
将每天的输入和输出拆点，建成二分图的样子
然后搞一搞，详见Sengxian’s Blog
之前直接建成时间线来跑，结果血wa
后来发现，那么建图根本没法保证每一天满流啊！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const int INF = 100000000;

int head[N],nxt[N],to[N],cost[N],flow[N],dis[N],inq[N];
int n,st,sc,ft,fc,arr[N],S,T,p,sur[N],FLOW[N]; 
queue<int> que;
 
inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

#define id(x,ty) ((x)*2+ty)
inline void Add_Edge(int u, int v, int f, int c) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline int SPFA() {
	memset(dis,127,sizeof(dis));
	memset(FLOW,0,sizeof(FLOW));
	que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
	
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
			dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
			FLOW[to[i]] = min(FLOW[w], flow[i]);
			if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
		}
	} return FLOW[T];
}

inline int MCMF() {
	int ret = 0;
	for (int w=T,f;f=SPFA();w=T) 
		for (int t=sur[w];w!=S;t=sur[w]) 
			flow[t] -= f, 
			flow[t^1] += f,
			ret += cost[t]*f, 
			w = to[t^1];
	return ret;
}

int main(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	n = read(); S = 0; T = 1;
	for (int i=1;i<=n;i++) arr[i] = read();
	p = read(); ft = read(); fc = read(); st = read(); sc = read();
	for (int i=1;i<=n;i++) Add_Edge(S,id(i,0),arr[i],0), Add_Edge(id(i,1),T,arr[i],0);
	for (int i=1;i<n;i++) Add_Edge(id(i,0),id(i+1,0),INF,0);
	for (int i=1;i<=n;i++) if (i + ft <= n) Add_Edge(id(i,0),id(i+ft,1),INF,fc);
	for (int i=1;i<=n;i++) if (i + st <= n) Add_Edge(id(i,0),id(i+st,1),INF,sc);
	for (int i=1;i<=n;i++) Add_Edge(S,id(i,1),INF,p);
	printf("%d\n",MCMF());
	return 0;
}

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1877
数据生成器：http://paste.ubuntu.com/23172606/

喜闻乐见大水题！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200*2+9;
const int M = 50000+9;
const int INF = 100000000;

int head[N],dis[N],nxt[M],cost[M],to[M],flow[M]; 
int n,m,S,T,F,C,inq[N],cur[N],sur[N];
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

#define id(x,ty) ((x)+n*(ty))
inline void Add_Edge(int u, int v, int f, int c) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline bool SPFA(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(S); inq[S] = 1; cur[S] = INF;
	
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=nxt[i]) if (flow[i])
			if (!~dis[to[i]] || dis[to[i]] > dis[w] + cost[i]) {
				sur[to[i]] = i;
				dis[to[i]] = dis[w] + cost[i]; 
				cur[to[i]] = min(flow[i], cur[w]);
				if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
			}
	}
	return ~dis[T];
}

inline void MCMF(){
	for (int w=T;SPFA();w=T) {
		F += cur[T];
		while (w != S) {
			flow[sur[w]] -= cur[T];
			flow[sur[w]^1] += cur[T];
			C += cur[T]*cost[sur[w]];
			w = to[sur[w]^1];
		}
	}
}

int main(){
	n = read(); m = read(); S = id(1,1); T = id(n,0);
	for (int i=2;i<n;i++) Add_Edge(id(i,0),id(i,1),1,0);
	for (int i=1,u,v,c;i<=m;i++) 
		u = read(), v = read(), c = read(),
		Add_Edge(id(u,1),id(v,0),1,c);
	MCMF();
	printf("%d %d\n",F,C);
	return 0;
}