# 7 条题解

• @ 2017-10-07 10:39:44
``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> a;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
cw[x].push_back(y);
c[x].push_back(c_v);
p[x].push_back(p_v);
ce[y].push_back(cw[x].size()-1);
cw[y].push_back(x);
c[y].push_back(0);
p[y].push_back(-p_v);
ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
f.resize(0);
f.resize(cw.size(),0);
f[s]=oo_max;
e.resize(0);
e.resize(cw.size(),-1);
u.resize(0);
u.resize(cw.size(),oo_max);
u[s]=0;
pre.resize(0);
pre.resize(cw.size(),-1);
pre[s]=s;
vis.resize(0);
vis.resize(cw.size(),0);
for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
{
int now=q.front();
for (int i=0;i<cw[now].size();i++)
if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
{
f[cw[now][i]]=min(c[now][i],f[now]);
e[cw[now][i]]=i;
u[cw[now][i]]=u[now]+p[now][i];
pre[cw[now][i]]=now;
if (vis[cw[now][i]]==0)
vis[cw[now][i]]=1,q.push_back(cw[now][i]);
}
}
(*flow)=f[t];
(*cost)=u[t];
return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
int temp_flow,temp_cost;
while (bfs_1(s,t,&temp_flow,&temp_cost))
{
for (int i=t;i!=s;i=pre[i])
c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
(*flow)+=temp_flow;
(*cost)+=(temp_cost*temp_flow);
}
}

int main()
{
while (~scanf("%d%d",&n,&m))
{
cw.resize(0);
cw.resize(n+3);
ce.resize(0);
ce.resize(cw.size());
c.resize(0);
c.resize(cw.size());
p.resize(0);
p.resize(cw.size());
for (int i=0;i<cw.size();i++)
{
cw[i].resize(0);
ce[i].resize(0);
c[i].resize(0);
p[i].resize(0);
}
a.resize(0);
a.resize(n+2,0);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}
for (int i=1;i<=n+1;i++)
{
int flow=a[i]-a[i-1];
if (flow>0)
else if (flow<0)
if (i>1)
}
int ans_flow=0,ans_cost=0;
min_cost_max_flow_1(0,cw.size()-1,&ans_flow,&ans_cost);
printf("%d\n",ans_cost);
}
}
``````
• @ 2017-10-07 10:40:08

很H2O的题

• @ 2018-06-24 08:41:13

看成线性规划，对偶之后可以证明得到的矩阵是全幺模的，直接单纯形。

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
const ll INF=0x3f3f3f3f3f3f3f3fLL;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
#ifdef LOCAL
freopen("1061.txt","r",stdin);
#endif
bufpos=0;
}
#if NEG
bool isneg;
int val=0;
for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
bufpos+=(isneg=buf[bufpos]=='-');
for(;isdigit(buf[bufpos]);bufpos++)
val=val*10+buf[bufpos]-'0';
return isneg?-val:val;
}
#else
int val=0;
for(;!isdigit(buf[bufpos]);bufpos++);
for(;isdigit(buf[bufpos]);bufpos++)
val=val*10+buf[bufpos]-'0';
return val;
}
#endif
for(;isspace(buf[bufpos]);bufpos++);
return buf[bufpos++];
}
int cur=0;
for(;isspace(buf[bufpos]);bufpos++);
for(;!isspace(buf[bufpos]);bufpos++)
s[cur++]=buf[bufpos];
s[cur]='\0';
return cur;
}
int n,m;
ll a[10005][1005];
void pivot(int e,int l){ //e,n+l;
ll tmp=-a[l][e];
a[l][e]=-1;
for(int i=0;i<=n;i++)
a[l][i]/=tmp;
for(int i=0;i<=m;i++)
if (i!=l && a[i][e]){
ll tmp=a[i][e];
a[i][e]=0;
if (tmp==1)
for(int j=0;j<=n;j++)
a[i][j]+=a[l][j];
else if (tmp==-1)
for(int j=0;j<=n;j++)
a[i][j]-=a[l][j];
else for(int j=0;j<=n;j++)
a[i][j]+=tmp*a[l][j];
}
}
ll work(){
while(1){
ll mx=0,x=0;
for(int i=1;i<=n;i++)
if (a[0][i]>mx)
mx=a[0][i],x=i;
if (!x)
return a[0][0];
ll mn=INF,y=0;
for(int i=1;i<=m;i++){
if (a[i][x]>=0)
continue;
ll tmp=-a[i][0]/a[i][x];
if (tmp<mn)
mn=tmp,y=i;
}
if (!y){
puts("WTF");
return INF;
}
pivot(x,y);
}
}
int main(){
init();
for(int i=1;i<=n;i++)
for(int i=1;i<=m;i++){
for(int j=l;j<=r;j++)
a[i][j]=-1;
}
printf("%lld",work());
}
``````
• @ 2017-03-02 09:41:26

神奇的费用流....
Orz楼下学长QwQ

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

const int MAXN = 1005, MAXM = 200000;
struct node {
int to, next, f, c, neg;
} edge[MAXM];
void push(int i, int j, int k, int l)
{
//printf("%d--%d,%d-->%d\n", i, k, l, j);
++top, edge[top] = (node) {j, head[i], k, l, top+1}, head[i] = top;
++top, edge[top] = (node) {i, head[j], 0, -l, top-1}, head[j] = top;
}
int n, m;
int S = 1002, T = 1003;
const int inf = 23333333;

void push_lim(int i, int j, int low)
{
push(S, j, low, 0);
push(i, T, low, 0);
push(i, j, inf, 0);
}

int vis[MAXN], dis[MAXN];
int pre[MAXN], pre_edge[MAXN];
queue<int> que;

bool spfa()
{
memset(vis, 0, sizeof vis);
memset(dis, 127/3, sizeof dis);
memset(pre, 0, sizeof pre);
vis[S] = 1, dis[S] = 0, que.push(S);
while (!que.empty()) {
int tp = que.front(); que.pop(); vis[tp] = 0;
for (int i = head[tp]; i; i = edge[i].next) {
if (edge[i].f == 0 || dis[edge[i].to] <= dis[tp] + edge[i].c) continue;
dis[edge[i].to] = dis[tp] + edge[i].c;
pre[edge[i].to] = tp;
pre_edge[edge[i].to] = i;
if (!vis[edge[i].to])
vis[edge[i].to] = 1, que.push(edge[i].to);
}
}
return dis[T] <= inf;
}

int work(int &cost)
{
int ans = inf;
for (int i = T; i != S; i = pre[i]) ans = min(ans, edge[pre_edge[i]].f);
for (int i = T; i != S; i = pre[i]) edge[pre_edge[i]].f -= ans, edge[edge[pre_edge[i]].neg].f += ans;
cost += dis[T]*ans;
//cout << dis[T] << "--" << endl;
//cin.get();
return ans;
}

int mcf(int &cost)
{
int ans = 0;
while (spfa()) ans += work(cost);
return ans;
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int u; scanf("%d", &u);
push_lim(i, i+1, u);
}
for (int i = 1; i <= m; i++) {
int s, t, c; scanf("%d%d%d", &s, &t, &c);
push(t+1, s, inf, c);
}
int cost = 0;
mcf(cost);
cout << cost << endl;
return 0;
}
``````
• @ 2016-06-13 21:53:22

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int maxN=1005;
const int maxM=10005;
const int inf=0x7f7f7f7f;

struct Edge
{
int to;
int next;
int capacity;
int cost;

void assign(int t,int n,int cp,int co)
{
to=t,next=n,capacity=cp,cost=co;
}
};

Edge elist[maxM*20];
int ecnt;
int src,sink;

void initEdge()
{
ecnt=0;
}

inline void addEdge(int from,int to,int capacity,int cost)
{
}

int N,M;
int A[maxN];
int S[maxM],T[maxM],C[maxM];

void input()
{
scanf("%d%d",&N,&M);
A[0]=0; A[N+1]=0;
for(int i=1;i<=N;i++) scanf("%d",A+i);
for(int i=1;i<=M;i++)
scanf("%d%d%d",S+i,T+i,C+i);
}

void buildGraph()
{
src=0; sink=N+2;
initEdge();
for(int i=1;i<=N+1;i++)
{
}
for(int i=1;i<=N;i++)
for(int i=1;i<=M;i++)
}

int dist[maxN];
int prevV[maxN];
int prevE[maxN];
bool inq[maxN];
std::queue<int> que;

bool spfa()
{
memset(dist,0x7f,sizeof(dist));
dist[src]=0;
memset(inq,0,sizeof(inq));
que.push(src);
prevV[src]=prevE[src]=-1;
while(!que.empty())
{
int cur=que.front();
que.pop(); inq[cur]=false;
if(elist[e].capacity)
{
int& to=elist[e].to;
int& co=elist[e].cost;
if(dist[to]>dist[cur]+co)
{
dist[to]=dist[cur]+co;
prevV[to]=cur;
prevE[to]=e;
if(!inq[to])
{
que.push(to);
inq[to]=true;
}
}
}
}
return dist[sink]<inf;
}

int minCostFlow()
{
int res(0);
while(spfa())
{
int maxf=inf;
for(int e=prevE[sink],v=sink;e!=-1;v=prevV[v],e=prevE[v])
maxf=std::min(maxf,elist[e].capacity);
for(int e=prevE[sink],v=sink;e!=-1;v=prevV[v],e=prevE[v])
{
res+=maxf*elist[e].cost;
elist[e].capacity-=maxf;
elist[e^1].capacity+=maxf;
}
}
return res;
}

int main()
{
input();
buildGraph();
printf("%d\n",minCostFlow());
return 0;
}

Orz ByVoid大神

• @ 2016-05-18 14:51:20

建模好难想得到，费用流……
```c++
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int INF=2147483647;

struct Ed
{
int from,to,cap,cost,flow;
Ed(int a,int b,int c=INF,int e=0,int d=0) : from(a),to(b),cap(c),cost(e),flow(d) {};
};

struct Po
{
int th;
vector<int > id_edges;
Po(int a) : th(a) {};
};

int n,m;
long long int all_cost=0;
int a[1100],c[1100],p[1100],leastpe[1100];
vector<Ed> edges;
vector<Po> points;
bool inqu[1100];

void add_edges(int from,int to,int cap,int cost)
{
edges.push_back(Ed(from,to,cap,cost));
points[from].id_edges.push_back(edges.size()-1);
edges.push_back(Ed(to,from,0,-1*cost));
points[to].id_edges.push_back(edges.size()-1);
/*return points[from].id_edges[points[from].id_edges.size()-1];*/
}

bool SPFA()
{
memset(a,0,sizeof(a));
memset(c,-1,sizeof(c));
memset(p,0,sizeof(p));
memset(inqu,0,sizeof(inqu));
queue<int> Q;
a[0]=INF; c[0]=0;
Q.push(0); inqu[0]=true;
while(!Q.empty())
{
int k=Q.front();Q.pop(); inqu[k]=false;
Po &now=points[k];

for(int i=0;i<(int)now.id_edges.size();i++)
{
Ed &now_ed=edges[now.id_edges[i]];
if(now_ed.flow<now_ed.cap&&(c[now_ed.to]==-1||c[now_ed.to]>c[now.th]+now_ed.cost))
{
a[now_ed.to]=min(a[now.th],now_ed.cap-now_ed.flow);
p[now_ed.to]=now.id_edges[i];
c[now_ed.to]=c[now.th]+now_ed.cost;
if(!inqu[now_ed.to]) { Q.push(now_ed.to); inqu[now_ed.to] =true; }
}
}
}
if(a[n+2]==0) return false;
all_cost+=(long long int)a[n+2]*(long long int)c[n+2];
for(int i=n+2;i!=0;i=edges[p[i]].from)
{
edges[p[i]].flow+=a[n+2];
edges[p[i]^1].flow-=a[n+2];
}
return true;
}

int main()
{
/*freopen("employee.in","r",stdin);*/
memset(leastpe,0,sizeof(leastpe));
scanf("%d%d",&n,&m);
points.push_back(Po(0));
for(int i=1;i<=n;i++)
{
scanf("%d",&leastpe[i]);
points.push_back(Po(i));
}
points.push_back(Po(n+1));points.push_back(Po(n+2));
for(int i=1;i<=n+1;i++)
for(int i=1;i<=m;i++)
{
int b,e,c;
scanf("%d%d%d",&b,&e,&c);
}

while(SPFA()) {}

printf("%lld\n",all_cost);
return 0;
}
```

• @ 2016-05-18 14:50:09
``````
``````
• @ 2013-11-03 12:44:08

这题的难度是10？第一次见到,一直以为4就是最高了。。。 ZKW费用流。。。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 648 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 860 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1020 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1236 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 1728 KiB, score = 10
Accepted, time = 185 ms, mem = 1728 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 1010

struct node {
int t,f,c;
node *next,*pair;
node (){
next=pair=NULL;
}
};

void INSERT(int s,int t,int f,int c){
node *p=new(node);
p->t=t;
p->f=f;
p->c=c;
p=new(node);
p->t=s;
p->f=0;
p->c=-c;
}

int n,m;
int S,T;
int a[MAXN];

int dist[MAXN];
bool f[MAXN];
int cost=0;

int aug(int v,int flow){
if (v==T){
cost+=flow*dist[S];
return flow;
}
f[v]=false;
int rec=0;
if (p->f&&f[p->t]&&dist[v]==dist[p->t]+p->c){
int ret=aug(p->t,min(flow-rec,p->f));
p->f-=ret;
p->pair->f+=ret;
if ((rec+=ret)==flow){
return flow;
}
}
}
return rec;
}

bool relabel(){
int delta=0x7fffffff;
for (int i=0;i++<T;){
if (!f[i]){
if (p->f&&f[p->t]){
delta=min(delta,dist[p->t]+p->c-dist[i]);
}
}
}
}
if (delta==0x7fffffff){
return false;
}
for (int i=0;i++<T;){
if (!f[i]){
dist[i]+=delta;
}
}
return true;
}

int main(){
scanf("%d%d",&n,&m);
S=n+2;
T=S+1;
int x=0;
for (int i=0;i++<n;){
scanf("%d",&a[i]);
if (a[i]-x>=0){
INSERT(S,i,a[i]-x,0);
} else INSERT(i,T,x-a[i],0);
x=a[i];
}
INSERT(n+1,T,a[n],0);
for (int i=0;i++<m;){
int s,t,c;
scanf("%d%d%d",&s,&t,&c);
INSERT(s,t+1,0x7fffffff,c);
}
for (int i=1;i++<n+1;){
INSERT(i,i-1,0x7fffffff,0);
}
memset(dist,0,sizeof(dist));
do {
do {
memset(f,true,sizeof(f));
} while (aug(S,0x7fffffff));
} while (relabel());
printf("%d\n",cost);
return 0;
}

• @ 2013-11-03 12:45:34

哦。看走眼了。。。这题是没有难度。。。提交10....

• 1

ID
1825

4

(无)

206

88

43%

2