2 条题解
-
0
题目只求是否有合法方案,那么 最短路模型 和 最长路模型 都可以。 这里选择最短路模型。 约束条件的推导: 设s[i]表示从1~i这个区间内有多少个点 那么每个约束条件可以表示为 s[ai+bi]-s[ai-1]>ci(gt) -> ci++ -> s[ai+bi]-s[ai-1]>=ci(gt) -> s[ai+bi]-ci >=s[ai-1] -> G[ai+bi].push_back({ai-1,-ci});
s[ai+bi]-s[ai-1]<ci(lt) -> ci-- -> s[ai+bi]-s[ai-1]<=ci(lt) -> s[ai-1]+ci >=s[ai+bi] -> G[ai-1].push_back({ai+bi,ci});
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> G[110]; int st, ed, d[110], dd[110]; bool v[110]; int spfa() { memset(d, 63, sizeof(d)); memset(dd, 0, sizeof(dd)); memset(v, 0, sizeof(v)); queue<int> q; for(int i = st; i <= ed; i++) q.push(i), v[i] = 1; d[st] = 0; while(!q.empty()) { int x = q.front(); q.pop(); v[x] = 0; for(auto i : G[x]) { int y = i.first, w = i.second; if(d[y] > d[x] + w) { d[y] = d[x] + w; dd[y] = dd[x] + 1; if(dd[y] > (ed - st + 1)) return 0; if(v[y] == 0) q.push(y), v[y] = 1; } } } return 1; } int main() { int n, m; while(scanf("%d", &n) && n) { scanf("%d", &m); for(int i = 0; i <= 109; i++) G[i].clear(); st = 110, ed = 0; for(int i = 1, x, y, c; i <= m; i++) { char ss[10]; scanf("%d%d%s%d", &x, &y, ss, &c); x++; y++; if(ss[0] == 'g') G[x + y].push_back({x - 1, -(c + 1)}); else G[x - 1].push_back({x + y, c - 1}); ed = max(ed, x + y); st = min(st, x - 1); } if(!spfa()) printf("successful conspiracy\n");//不等式组无解,无法得到想要的答案 else printf("lamentable kingdom\n");//反之则有解 } return 0; } -
0
/* 题目只求是否有合法方案,那么 最短路模型 和 最长路模型 都可以。 这里选择最短路模型。 约束条件的推导: 设s[i]表示从1~i这个区间内有多少个点 那么每个约束条件可以表示为 s[ai+bi]-s[ai-1]>ci(gt) -> ci++ -> s[ai+bi]-s[ai-1]>=ci(gt) -> s[ai+bi]-ci >=s[ai-1] -> G[ai+bi].push_back({ai-1,-ci}); s[ai+bi]-s[ai-1]<ci(lt) -> ci-- -> s[ai+bi]-s[ai-1]<=ci(lt) -> s[ai-1]+ci >=s[ai+bi] -> G[ai-1].push_back({ai+bi,ci}); */ #include<bits/stdc++.h> using namespace std; vector< pair<int,int> > G[110]; int st,ed,d[110],dd[110];bool v[110]; int spfa() { memset(d,63,sizeof(d)); memset(dd,0,sizeof(dd)); memset(v,0,sizeof(v)); queue<int>q;for(int i=st;i<=ed;i++)q.push(i),v[i]=1; d[st]=0; while(!q.empty()) { int x=q.front();q.pop();v[x]=0; for(auto i:G[x]) { int y=i.first,w=i.second; if(d[y]>d[x]+w) { d[y]=d[x]+w; dd[y]=dd[x]+1;if(dd[y]>(ed-st+1))return 0; if(v[y]==0)q.push(y),v[y]=1; } } } return 1; } int main() { int n,m; while(scanf("%d",&n) && n) { scanf("%d",&m); for(int i=0;i<=109;i++)G[i].clear(); st=110,ed=0; for(int i=1,x,y,c;i<=m;i++) { char ss[10];scanf("%d%d%s%d",&x,&y,ss,&c);x++;y++; if(ss[0]=='g')G[x+y].push_back({x-1,-(c+1)}); else G[x-1].push_back({x+y,c-1}); ed=max(ed,x+y); st=min(st,x-1); } if(!spfa())printf("successful conspiracy\n");//不等式组无解,无法得到想要的答案 else printf("lamentable kingdom\n");//反之则有解 } return 0; }
- 1
信息
- ID
- 701
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 72
- 已通过
- 15
- 上传者