AC通道：
然后codevs上也有，可以先去codevs上交一发[你看我这广告打的好吧= =]
BYvoid的题解写的比较清楚，也有图有样例，很良心：
先看完上面的博客吧...
然后BYvoid看上去是推的式子也很好列，因为你观察X(i)的正负，因为每次都是相邻的相减嘛，又因为每个人都是连续一段的，所以正号出现在第l[i]个式子中，负号出现在第r[i]+1个式子中。
然后y[i]就更简单了，正的出现在i+1，负的出现在i，然后初始建图部分就很好打了。
然后这题SPFA跑得有点慢= =。尽管加了一个SLF优化[不太记得名字了]，还一个是LLL优化，据说两个在一起才是最好？
#include#include #include #include using namespace std;const int maxn=1010;const int maxm=10010;const int INF=0x3f3f3f3f;struct Node{ int data,next,low,cost;}node[(maxm<<1)+(maxn<<2)];#define www node[point].low#define now node[point].data#define ccc node[point].cost#define then node[point].nextint n,m,ans,cnt;int s,t;int a[maxn],head[maxn];int dis[maxn],pre[maxn];bool inq[maxn];deque q;void add(int u,int v,int w,int c){ node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;node[cnt].cost=c;head[u]=cnt++; node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=0;node[cnt].cost=-c;head[v]=cnt++;}bool SPFA(){ memset(dis,0x3f,sizeof(dis)); int x,Low=INF; q.push_back(s);dis[s]=0;pre[s]=pre[t]=-1; while(!q.empty()){ x=q.front();q.pop_front();inq[x]=false; for(int point=head[x];point!=-1;point=then) if(www && dis[now]>dis[x]+ccc){ dis[now]=dis[x]+ccc;pre[now]=point^1; if(!inq[now]){ if(q.empty() || dis[q.front()]>dis[now]) q.push_front(now); else q.push_back(now); inq[now]=true; } } } if(pre[t]<0) return false; for(int point=pre[t];point!=-1;point=pre[now]) Low=min(Low,node[point^1].low); for(int point=pre[t];point!=-1;point=pre[now]) node[point^1].low-=Low,www+=Low; ans+=dis[t]*Low; return true;}int main(){#ifndef ONLINE_JUDGE freopen("1061.in","r",stdin); freopen("1061.out","w",stdout);#endif int u,v,c; scanf("%d%d",&n,&m); t=n+2; for(int i=s;i<=t;i++) head[i]=-1; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n+1;i++){ if(a[i]-a[i-1]>0) add(s,i,a[i]-a[i-1],0); else add(i,t,a[i-1]-a[i],0); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&c); add(u,v+1,INF,c); } for(int i=1;i<=n;i++) add(i+1,i,INF,0); while(SPFA()); printf("%d",ans); return 0;}
然后用zkw就快了很多，毕竟只是稀疏图。
#include#include #include using namespace std;const int maxn=1010;const int maxm=10010;const int INF=0x3f3f3f3f;struct Node{ int data,next,low,cost;}node[(maxm<<1)+(maxn<<2)];#define www node[point].low#define now node[point].data#define ccc node[point].cost#define then node[point].nextint n,m,ans,cnt;int s,t;int a[maxn],head[maxn],cur[maxn];int dis[maxn],pre[maxn];bool vis[maxn];void add(int u,int v,int w,int c){ node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;node[cnt].cost=c;head[u]=cnt++; node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=0;node[cnt].cost=-c;head[v]=cnt++;}int dfs(int x,int low){ if(x==t) return low; int Low;vis[x]=true; for(int &point=cur[x];point!=-1;point=then) if(www && !vis[now] && dis[now]+ccc==dis[x]){ Low=dfs(now,min(low,www)); if(Low){ www-=Low,node[point^1].low+=Low; return Low; } } return 0;}bool modify(){ int ad=INF; for(int i=s;i<=t;i++) if(vis[i]) for(int point=head[i];point!=-1;point=then) if(www && !vis[now]) ad=min(ad,dis[now]-dis[i]+ccc); if(ad==INF) return false; for(int i=s;i<=t;i++) if(vis[i]) vis[i]=false,dis[i]+=ad; return true;}int main(){#ifndef ONLINE_JUDGE freopen("1061.in","r",stdin); freopen("1061.out","w",stdout);#endif int u,v,c; scanf("%d%d",&n,&m); t=n+2; for(int i=s;i<=t;i++) head[i]=-1; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n+1;i++){ if(a[i]-a[i-1]>0) add(s,i,a[i]-a[i-1],0); else add(i,t,a[i-1]-a[i],0); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&c); add(u,v+1,INF,c); } for(int i=1;i<=n;i++) add(i+1,i,INF,0); int flag; do{ for(int i=s;i<=t;i++) cur[i]=head[i]; while(flag=dfs(s,INF)) ans+=dis[s]*flag; }while(modify()); printf("%d",ans); return 0;}
这题告诉我们线性规划和网络流之间是有联系的...