2020-2021:teams:legal_string:组队训练比赛记录:contest5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest5 [2021/08/03 21:20] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest5 [2021/08/04 10:52] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 128: | 行 128: | ||
| for(int u:ans) | for(int u:ans) | ||
| space(u); | space(u); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== G. Berland Post ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定若干条形如 $x_v+b_i\le x_u+T$ 的限制，求最小的 $T$ 以及这种情况下的一组合法解 $(x_1,x_2\cdots x_n)$。 | ||
| + | |||
| + | 其中，某些 $x_i$ 的值已经固定。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 将方程转化为 $x_v\le x_u+T-b_i$，考虑二分 $T$ 然后差分约束求解。 | ||
| + | |||
| + | 设超级源点为 $s$。关于点权的限制，对于无限制的 $x_i$，连边 $(s,i,\infty),(i,s,\infty)$，表示 $-\infty\le x_i\le \infty$。 | ||
| + | |||
| + | 对于固定的 $x_i$，连边 $(s,i,v),(i,s,-v)$，表示 $v\le x_i\le v$。时间复杂度 $O(nm\log V)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e3+5,MAXM=4e3+5,SPV=2e5; | ||
| + | const double inf=1e15,infv=1e7,eps=1e-7,eps2=1e-9; | ||
| + | int read_int(){ | ||
| + | int t=0;bool sign=false;char c=getchar(); | ||
| + | while(c==' '||c=='\r'||c=='\n')c=getchar(); | ||
| + | if(c=='?')return SPV; | ||
| + | if(c=='-')sign=true,c=getchar(); | ||
| + | while(isdigit(c)){ | ||
| + | t=t*10+c-'0'; | ||
| + | c=getchar(); | ||
| + | } | ||
| + | return sign?-t:t; | ||
| + | } | ||
| + | struct Edge{ | ||
| + | int to,next; | ||
| + | double w; | ||
| + | }edge[MAXM<<1]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v,double w){ | ||
| + | ++edge_cnt; | ||
| + | edge[edge_cnt].to=v; | ||
| + | edge[edge_cnt].w=w; | ||
| + | edge[edge_cnt].next=head[u]; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | namespace SPFA{ | ||
| + | double dis[MAXN]; | ||
| + | int len[MAXN]; | ||
| + | bool inque[MAXN]; | ||
| + | bool solve(int src,int n){ | ||
| + | queue<int>q; | ||
| + | _rep(i,1,n){ | ||
| + | inque[i]=false; | ||
| + | len[i]=0; | ||
| + | dis[i]=inf; | ||
| + | } | ||
| + | dis[src]=0;len[src]=1; | ||
| + | q.push(src); | ||
| + | inque[src]=true; | ||
| + | while(!q.empty()){ | ||
| + | int u=q.front();q.pop(); | ||
| + | inque[u]=false; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(dis[v]>dis[u]+edge[i].w+eps2){ | ||
| + | dis[v]=dis[u]+edge[i].w; | ||
| + | len[v]=len[u]+1; | ||
| + | if(len[v]>n) | ||
| + | return false; | ||
| + | if(!inque[v]){ | ||
| + | q.push(v); | ||
| + | inque[v]=true; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | } | ||
| + | struct Edge2{ | ||
| + | int u,v,w; | ||
| + | }; | ||
| + | vector<Edge2> edges; | ||
| + | int a[MAXN]; | ||
| + | bool check(int n,double T){ | ||
| + | int s=++n; | ||
| + | edge_cnt=0; | ||
| + | _rep(i,1,n) | ||
| + | head[i]=0; | ||
| + | _for(i,1,n){ | ||
| + | if(a[i]==SPV){ | ||
| + | Insert(s,i,infv); | ||
| + | Insert(i,s,infv); | ||
| + | } | ||
| + | else{ | ||
| + | Insert(s,i,a[i]); | ||
| + | Insert(i,s,-a[i]); | ||
| + | } | ||
| + | } | ||
| + | for(Edge2 e:edges) | ||
| + | Insert(e.v,e.u,T-e.w); | ||
| + | return SPFA::solve(s,n); | ||
| + | } | ||
| + | int main(){ | ||
| + | int n,m; | ||
| + | while(cin>>n>>m){ | ||
| + | edges.clear(); | ||
| + | _rep(i,1,n) | ||
| + | a[i]=read_int(); | ||
| + | while(m--){ | ||
| + | int u=read_int(),v=read_int(),w=read_int(); | ||
| + | edges.push_back(Edge2{u,v,w}); | ||
| + | } | ||
| + | double lef=0,rig=infv; | ||
| + | while(rig-lef>eps){ | ||
| + | double mid=(lef+rig)/2; | ||
| + | if(check(n,mid)) | ||
| + | rig=mid; | ||
| + | else | ||
| + | lef=mid; | ||
| + | } | ||
| + | printf("%.6lf\n",lef); | ||
| + | check(n,lef); | ||
| + | _rep(i,1,n) | ||
| + | printf("%.6lf ",SPFA::dis[i]); | ||
| + | puts(""); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest5.1627996843.txt.gz · 最后更改: 2021/08/03 21:20 由 jxm2001
