D2欧拉路，拓扑排序，和差分约束( 三 ) _字母

#include#include#includeconst int MAX=1e6+5;const int inf=0x3f3f3f3f;using namespace std;inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}int n,x,y,vis[MAX*2],dis[MAX*2],lin[MAX*2],tot,ans[MAX*2],a,b,c;struct gg{int y,next,v;}an[MAX];void init(int x,int y,int z){an[++tot].y=y;an[tot].v=z;an[tot].next=lin[x];lin[x]=tot;}queue q;int spfa(int s,int n){for (int i=0;idis[x]+an[i].v){dis[y]=dis[x]+an[i].v;if (!vis[y]){vis[y]=1,q.push(y);++ans[y];if (ans[y]>n) return -1;}}}}if(dis[n]==inf) return -2;return dis[n]; }int main(){int n=read(),x=read(),y=read();for (int i=1;i
View Code
第五题：
题目大意：银河系中有n个防御站排成一条直线，给定m条信息，每条信息的格式如下: P A B X代表A站在B站北方X光年处。V A B 代表A站在B站北方，而且距离至少为1光年。问是否存在这样的一个防御战排列满足上述要求，是输出，否输出。
dist[A] ? dist[B] ≥ X，表示A在B北边至少X光年位置。变形为： dist[B] d[i]，即d[i + 1] ? d[i] ≥ 1,即d[i] ? d[i + 1] ≤ ?1 。还有一个条件是相邻两个要跳跃的距离不可以大于D，可以写出另一个方程。有一点小问题就是建边的方向和跳跃的方向不同，我们要保证是向一个方向建图的。若从左到右建边，如果1在n的左面就从1到n跑SPFA，反之则从n到1跑最短路了。
暂无代码；
第七题：
题解：每天的工作情况都是一样的，我们只需要求出一天的即可。根据题意，令s[i]为一天内前i + 1个小时录用的人数。◆ 如果i ≥ 7,则s[i] ? s[i ? 8] ≥ R[i] ◆ 如果0 ≤ i < 7，则可以推出s[23] ? s[i + 16] + s[i] ≥ R[i] ◆ 同时每个时刻录用的人数有个上限，假设第i时刻最多可以录用的人数为b[i],则对于每一个i有0 ≤ s[i] ? s[i ? 1] ≤ b[i] 。第二个不等式中包含3个s数组的变量，这该怎么建图呢？枚举s[23]，那么这个量就是已知的了，因此不等式可以变为s[i] ? s[i + 16] ≥ R[i] ? s[23] 。既然s[23]是枚举的一天的录用人数的最小数目，我们建图之后求出的s[23]也应该为枚举的那个值。单调性，二分。
暂无代码;