33 条题解
-
2
ccnuzhang LV 9 @ 2009-09-18 17:40:01
额...奇怪了...
(1) s-> (1,2,...n)连一条容量为inf，费用为f的边;
(2) s->1 连一条容量为inf，费用为f的边，在连i->i+1容量为inf，费用为0的边.
这2种建图有区别吗?不明白...(1)WA,(2)Ac -
1
Sky1231 (sky1231) LV 10 @ 2017-07-13 17:19:47
#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,a,b,cn,ca,cb; 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_flow*temp_cost); } } int main() { while (~scanf("%d%d%d%d%d%d",&n,&a,&b,&cn,&ca,&cb)) { cw.resize(0); cw.resize(2*n+2); 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); } for (int i=1;i<=n;i++) { int x; scanf("%d",&x); add_edge_1(0,i,x,0); add_edge_1(i+n,cw.size()-1,x,0); add_edge_1(0,i+n,oo_max,cn); if (i+1<=n) add_edge_1(i,i+1,oo_max,0); if (i+a+1<=n) add_edge_1(i,i+n+a+1,oo_max,ca); if (i+b+1<=n) add_edge_1(i,i+n+b+1,oo_max,cb); } 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); } }-
很H2O的題
-
-
0
测试数据 #0: Accepted, time = 0 ms, mem = 588 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 584 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 676 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 676 KiB, score = 20
测试数据 #4: Accepted, time = 15 ms, mem = 672 KiB, score = 20
Accepted, time = 15 ms, mem = 676 KiB, score = 100
代码第一次只有40分。。看题解才知道和原题不一样，这个构图上有一点点区别。。
原题是需要a天洗完时，第i+a天就能用，但这个是i+a+1天，没差多少。。
构图是用二分图感觉好理解一点。。还是感觉有点不能理解为什么可以这么去想，还是要加油#include<iostream> #include<iomanip> #include<cstring> #include<vector> #include<sstream> #include<algorithm> #include<string> #include<cstdio> #include<math.h> #include<map> #include<cctype> #include<queue> #include<functional> #include<set> #define Mem(a,b) memset((a),(b),sizeof((a))) #define Sy system("pause") const int maxn = 1100; const int INF = 0x3f3f3f; using namespace std; struct MCMF{ struct Edge { int from, to, cap, flow, cost; Edge(int a, int b, int c, int d, int e) :from(a), to(b), cap(c), flow(d), cost(e) {} Edge(){} }; int n, m; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn], d[maxn], p[maxn], a[maxn]; void init(int n){ this->n = n; for (int i = 0; i < n; i += 1)G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap, int cost){ edges.push_back(Edge(from, to, cap, 0, cost)); edges.push_back(Edge(to, from, 0, 0, -cost)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BellmanFord(int s, int t, int & flow,int & cost){ for (int i = 0; i < n; i += 1) d[i] = INF; memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for (int i = 0; i < G[u].size(); i += 1){ Edge & e = edges[G[u][i]]; if (e.cap > e.flow && d[e.to] > d[u] + e.cost){ d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); if (!inq[e.to]){ Q.push(e.to); inq[e.to] = 1; } } } } if (d[t] == INF) return false; flow += a[t]; cost += d[t] * a[t]; for (int u = t; u != s; u = edges[p[u]].from){ edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } return true; } int MinCostMaxFlow(int s, int t, int & cost){ int flow = 0; cost = 0; while (BellmanFord(s, t, flow, cost)); return flow; } }; /* S: 0 DLi:[1,n] DRi:[n+1,2n] T:2n+1 */ int main(){ int n, a, b, f, fa, fb,tmp; scanf("%d %d %d %d %d %d", &n, &a, &b, &f, &fa, &fb); int S = 0, T = 2 * n + 1; MCMF D; D.init(2 * n + 2); for (int i = 1; i <= n; i += 1){ scanf("%d", &tmp); D.AddEdge(S, i, tmp, 0); D.AddEdge(i + n, T, tmp, 0); D.AddEdge(S, i + n, INF, f); if (i + 1 <= n) D.AddEdge(i, i + 1, INF, 0); if (i + a + 1<= n) D.AddEdge(i, i + n + a + 1, INF, fa); if (i + b + 1 <= n) D.AddEdge(i, i + n + b + 1, INF, fb); } int ans; D.MinCostMaxFlow(S, T, ans); printf("%d\n", ans); //Sy; return 0; } -
0
直接拿BZOJ超时的代码过来，居然还A了。。。。
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 504 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 492 KiB, score = 20
测试数据 #2: Accepted, time = 31 ms, mem = 1376 KiB, score = 20
测试数据 #3: Accepted, time = 31 ms, mem = 1412 KiB, score = 20
测试数据 #4: Accepted, time = 46 ms, mem = 1176 KiB, score = 20
Accepted, time = 108 ms, mem = 1412 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>using namespace std;
#define MAXN 2010
struct node {
node *next,*other;
int t,f,c;
};node *head[MAXN];
int n,a,b,fa,fb,f;
void INSERT(int s,int t,int f,int c){
node *p=new(node);
(*p).t=t;
(*p).f=f;
(*p).c=c;
(*p).next=head[s];
head[s]=p;
}int S,T;
int minc[MAXN],minf[MAXN],su[MAXN];
bool flag[MAXN];
node* d[MAXN];struct cmp{
bool operator()(int x,int y){
return minc[x]>minc[y];
}
};priority_queue<int,vector<int>,cmp>q;
/*
void OUT(){
for (int i=0;i++<T;){
printf("%d:\n",i);
node *p=head[i];
while (p!=NULL){
// if ((*p).f){
printf("%d %d %d\n",(*p).t,(*p).f,(*p).c);
// }
p=(*p).next;
}
printf("\n\n");
}
}
*/
int main(){
scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);
S=n*2+1;
T=S+1;
for (int i=0;i++<2*n+2;){
head[i]=NULL;
}
for (int i=0;i++<n;){
int x;
scanf("%d",&x);
INSERT(S,i,x,f);
INSERT(i,S,0,-f);
(*head[S]).other=head[i];
(*head[i]).other=head[S];
INSERT(S,n+i,x,0);
INSERT(n+i,S,0,0);
(*head[S]).other=head[n+i];
(*head[n+i]).other=head[S];
INSERT(i,T,x,0);
INSERT(T,i,0,0);
(*head[i]).other=head[T];
(*head[T]).other=head[i];
}
for (int i=0;i++<n;){
for (int j=i+a+1;j<=n;j++){
INSERT(n+i,j,0x7fffffff,fa);
INSERT(j,n+i,0,-fa);
(*head[n+i]).other=head[j];
(*head[j]).other=head[n+i];
}
for (int j=i+b+1;j<=n;j++){
INSERT(n+i,j,0x7fffffff,fb);
INSERT(j,n+i,0,-fb);
(*head[n+i]).other=head[j];
(*head[j]).other=head[n+i];
}
}
// OUT();
int min_cost=0;
while (1){
for (int i=0;i++<T;){
minc[i]=0x7fffffff;
}
minc[S]=su[S]=0;
minf[S]=0x7fffffff;
memset(flag,true,sizeof(flag));
while (!q.empty()){
q.pop();
}
q.push(S);
while (!q.empty()){
int v=q.top();
q.pop();
if (!flag[v]){
continue;
}
flag[v]=false;
if (v==T){
break;
}
node *p=head[v];
while (p!=NULL){
if ((*p).f&&minc[(*p).t]>(minc[v]+(*p).c)){
minc[(*p).t]=minc[v]+(*p).c;
q.push((*p).t);
flag[(*p).t]=true;
minf[(*p).t]=min(minf[v],(*p).f);
su[(*p).t]=v;
d[(*p).t]=p;
}
p=(*p).next;
}
}
if (minc[T]==0x7fffffff){
break;
}
int i=T;
// printf("!!!%d",T);
while (su[i]){
// printf("-%d(%d)",su[i],((*d[i]).c*minf[T]));
(d[i]).f-=minf[T];
((*d[i]).other).f+=minf[T];
min_cost+=((*d[i]).c*minf[T]);
i=su[i];
}
// printf("\n\n");
// max_flow+=minf[T];
}
printf("%d\n",min_cost);
// OUT();
return 0;
} -
0
JackDavid127 LV 10 @ 2010-07-08 20:11:14
傻傻的问一句：为什么叫“餐巾纸引发的血案”啊…………明明就是餐巾计划问题改版嘛。。。
是不是起得恐怖一点容易吸引人眼球啊。。。出题人有点不择手段啊……
-
0
这个...
我用的拆点，spfa最小费用流，(m:边数（包括反向边），n:点数)
第一次 40分...n=210,m=300*2;
最后三个错误号255-RE...第二次 40分...n=210,m=500*2;
第三个TLE 最后两个RE-255...第三次 AC...来了个暴力点的：
n=210,m=200*200*2;为啥m=500*2就不行呢...*2是反向边...
建图：第i天需要a[i]个
S向点i连flow=a[i],cost=0; 表示第I天结束；
i+n向T连flow=a[i],cost=0; 表示第i天刚刚开始；
S向i+n连flow=INF,cost=f;(买的价钱) 表示第i天买花费；
i向i+n+a连flow=INF,cost=fa; 表示a消毒...
i向i+n+b连flow=INF,cost=fa; 表示b消毒...
求最小割最大流...
这样需要m=500*2为啥不够呢... -
0
M36_slugger LV 10 @ 2010-03-08 21:26:15
晕，一开始当成餐巾问题，直接交，40分，后来发现了一个细微的差别：
餐巾问题第i天用完的餐巾洗了之后，如果洗餐巾花k天，那么第i+k天就可以用
…………
但这题，第i天用完之后开始洗，第i+k+1天才可以用，直接导致构图上的差别…………
之后费用流就行了 o(╯□╰)o -
0
ufo172849z LV 10 @ 2009-08-02 17:16:21
cgy4ever建的模型非常经典！
数据规模小，直接spfa增广就可以解决了。 -
0
lijian1987 LV 8 @ 2009-07-25 15:50:37
弱弱的问下 我建模的时候采用每一天都可以买毛巾怎么是错的。。。
即S->i都连一条容量为无穷 费用为f的便。。
不知道这种和S->1有什么区别。。 -
0
典型的最小费用最大流问题 …… 尤其是图是一个二分图 = =||
建图为 ：
procedure addarc (u , v , c , w : longint) ;
begin
// writeln (u,' - > ',v,' : ',c,' : ',w) ;
inc (tot) ; arc[tot].d := v ; arc[tot].c := c ; arc[tot].w := w ;
arc[tot].next := vr ; vr := tot ;
inc (tot) ; arc[tot].d := u ; arc[tot].c := 0 ; arc[tot].w := -w ;
arc[tot].next := vr[v] ; vr[v] := tot ;
end ;procedure solve ;
var i , c , n , New_cost , Q_time , Q_cost , S_time , S_cost
: longint ;
begin
fillchar (vr , sizeof (vr) , $ff) ; tot := -1 ;
// readln (n , New_cost , Q_time , Q_cost , S_time , S_cost) ;
readln (n , Q_time , S_time , New_cost , Q_cost , S_cost) ;
s := n + n + 1 ; t := s + 1 ; z := t ;
for i := 1 to n do begin
read (c) ;
addarc (s , i , c , 0) ;
addarc (n + i , t , c , 0) ;
addarc (s , n + i , oo , New_cost) ;
if (i + Q_time
ccnuzhang
LV 9
@ 2009-09-18 17:40:01
