17 条题解
-
2
Goodhao LV 10 @ 2018-08-05 14:03:15
感动啊终于学会差分约束了
之前理解的不到位。
本题的具体做法已经有很好的题解了，我讲一下对差分约束的理解。（如果你是像我一样拿这题入门差分约束的话可能会踩到很多坑）简单的说给定一些xi，和一些形如xi-xj<=某个常数的不等式组
差分约束就是通过bellmanford求出其中一组可行解。
这很重要，是其中一组可行解，也就是说还可以有别的解，而且你的解不一定是满足题目要求的最优性的，并且你把当前的解全部加上一个偏移量d也不一定能完全覆盖所有可行解（虽然可以得到无数组可行解）。
不过在本题中我们直接枚举答案，因此只需要存在一组可行解。差分约束建立了很多边，但是起点在哪里？怎么初始化dis呢？
做法是设立一个源点从它出发向其他所有点连权值为0的边，然后把它的dis设为0，把它当作起点。
这个做法很寻常，但是这样做的问题是，比如说你输出一下dis数组会发现为什么一些dis都是负数，但是我们的答案显然是正的，这里的dis到底是什么意思。
刚才说过我们可以通过偏移来得到无数组可行解，因为任意两个x之间的差永远不变，有点像物理里的势能一样，我们不在乎哪里是零势能，我们自行规定即可。于是我们规定一个点是零势能，点0，那么即使从我们选定的源点出发到点0的dis为负也不代表什么，这是“势能差”，要得到真正的势能，要把最终求好的所有dis加上dis[0]，也就是dis[x]-dis[0]才是我们真正想要的值这个理解以后，当你想对一个x进行约束比如让它=1的时候就不会直接在dis里设置dis[x]=1
而是dis[x]-dis[0]=1，变成两个不等式:
dis[x]-dis[0]<=1
dis[0]-dis[x]<=-1 （即dis[x]-dis[0]>=1）#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long const int N=100000+10; const int inf=0x3f3f3f3f; const ll mod=7654321; const double PI=3.1415926; const double eps=1e-8; int T; int n; int need[30]; int have[30]; int d[30]; struct edge { int to,w; }; vector<edge> g[30]; void insert(int x,int y,int w) { g[x].pb(edge{y,w}); } bool bellmanford() { memset(d,0x3f,sizeof d); d[25]=0; FOR(i,26) { REP(j,0,25) { for (int k=0;k<g[j].size();k++) { int to=g[j][k].to,w=g[j][k].w; if (d[to]>d[j]+w) { if (i==26) return 1; d[to]=d[j]+w; } } } } return 0; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>T; while (T--) { FOR(i,24) cin>>need[i]; cin>>n; memset(have,0,sizeof have); FOR(i,n) { int t;cin>>t; ++have[t+1]; } bool ok=0; REP(sum,0,n) { REP(i,0,25) g[i].clear(); REP(i,0,24) insert(25,i,0); FOR(i,24) insert(i,i-1,0); FOR(i,24) insert(i-1,i,have[i]); // s[0]=0 REP(i,8,24) insert(i,i-8,-need[i]); FOR(i,7) insert(i,i+16,sum-need[i]); insert(24,0,-sum); insert(0,24,sum); if (bellmanford()==0) { ok=1; cout<<sum<<endl; break; } } if (!ok) cout<<"No Solution"<<endl; } return 0; } -
0
/* 差分约束 http://www.cnblogs.com/fraud/p/4304350.html 和区间一起的在论文中有 http://wenku.baidu.com/view/685fbe1e650e52ea5518981a.html?from=related */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int MAXN=1005; const int INF=(1<<30)-1; struct Edge { int to,nxt,w; Edge() { to=nxt=w=-1; } }e[MAXN]; int first[MAXN]; int t,n; int tot; int d[MAXN]; int in[MAXN]; int cnt[MAXN]; int R[MAXN]; int num[MAXN]; int inihead[MAXN]; queue<int> q; void inline Add_Edge(int x,int y,int w) { tot++; e[tot].to=y; e[tot].w=w; e[tot].nxt=first[x]; first[x]=tot; } void init() { int a; for(int i=1;i<=24;i++) cin>>R[i]; cin>>n; memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) { cin>>a; num[a+1]++; } tot=0; memset(first,-1,sizeof(first)); memset(e,-1,sizeof(-1)); for(int i=1;i<=24;i++) { if(i>7) Add_Edge(i-8,i,R[i]); Add_Edge(i,i-1,-num[i]); Add_Edge(i-1,i,0); } for(int i=0;i<25;i++) inihead[i]=first[i]; } bool SPFA(int mid) { for(int i=0;i<=24;i++) d[i]=-INF,in[i]=0,cnt[i]=0; q.push(0); in[0]=1; cnt[0]++; d[0]=0; while(!q.empty()) { int x=q.front(); q.pop(); in[x]=0; for(int i=first[x];i!=-1;i=e[i].nxt) { int y=e[i].to; int w=e[i].w; if(d[y]<d[x]+w) { d[y]=d[x]+w; if(!in[y]) { q.push(y); in[y]=1; if(++cnt[y]>25) return false; } } } } return true; } int main() { cin>>t; while(t--) { init(); int l=0,r=n; int ans=INF; while(l<r) { int mid=(l+r)/2; for(int i=0;i<25;i++) first[i]=inihead[i]; for(int i=1;i<8;i++) Add_Edge(i+16,i,R[i]-mid); Add_Edge(0,24,mid); if(SPFA(mid)) { r=mid; ans=min(ans,mid); } else l=mid+1; } if(ans>n) cout<<"No Solution"<<endl; else cout<<ans<<endl; } return 0; } -
0
yzl609271536 LV 10 @ 2009-10-06 20:43:38
编译通过...
├ 测试数据 01：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms不错的差分约束题
一点点错 我调了N久
Goodhao
LV 10
@ 2018-08-05 14:03:15
- 1
