寒假牛客基础训练2"/>
寒假牛客基础训练2
处女座与宝藏:
题目大意:有n个宝箱，m个开关，每个宝箱有初始状态，规定0是打开，1是关闭，当全部为0时，可以获得宝藏，m个开关每个开关与 ki个宝箱相关联，按下开关时宝箱的状态会反转(0 变1 ，1 变0)。问处女座能否得到宝藏，每个宝箱至多与2个开关相关联。
由于每个宝箱只与2个开关相关联，根据宝箱的初始状态，可以得知这最多是一个二元的布尔逻辑运算，而每个开关有按和不按两种状态，两种状态必选其一，容易想到2-sat模型，即找到一个按或不按的集合，使得这些集合满足这个布尔运算，显然布尔运算是根据宝箱的状态而定的。分析一下建图即可
/*由于每个宝箱最多与两个开关有关联，因此是一个二元布尔逻辑运算每个宝箱有按和不按两种状态，本题是在求一个这样的集合使得所有宝箱的状态为0i为开关i,j为开关j，令i表示i开关要按，i+m表示不按,同理开关j 如果宝箱不和任何开关有关联:如果宝箱状态是1，说明该宝箱无法到达0状态，直接输出"NO" 如果宝箱只和一个开关有关联:如果宝箱状态是0,则必须要按; 建(i+m->i)的边使得不按产生矛盾如果宝箱状态是1，则必须不按；建(i->i+m)的边使得按会产生矛盾 如果宝箱和两个开关有关联:如果宝箱状态是0,则这两个开关要么都按要么都不按;建(i,j),(j,i),(i+m,j+m),(j+m,i+m)如果宝箱状态是1,则这两个开关只能按一个;建(i,j+m),(j,i+m),(i+m,j),(j+m,i)跑一下tarjan判断是否存在可行解即可
*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 4e5+10;
int a[maxn];
vector<int> g[maxn];
vector<int> h[maxn];
int belong[maxn],dfn[maxn],low[maxn],sta[maxn],vis[maxn],cnt,top,res;
void tarjan(int s){vis[s]=1;dfn[s]=low[s]=++cnt;sta[++top]=s;for(int i = 0; i < g[s].size(); i++){if(!dfn[g[s][i]]) tarjan(g[s][i]);if(vis[g[s][i]]==1) low[s]=min(low[s],low[g[s][i]]);}if(low[s]==dfn[s]){++res;do{belong[sta[top]]=res;vis[sta[top]]=0;}while(sta[top--]!=s);}
}
int main(){scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++)scanf("%d",&a[i]);for(int i = 1; i <= m; i++){int l,x;scanf("%d",&l);for(int j = 1; j <= l; j++){scanf("%d",&x);h[x].push_back(i);}}for(int i = 1; i <= n; i++){if(a[i]==1&&h[i].size()==0){puts("NO");return 0;}if(a[i]==0&&h[i].size()==1)g[h[i][0]].push_back(h[i][0]+m);else if(a[i]==1&&h[i].size()==1)g[h[i][0]+m].push_back(h[i][0]);else if(a[i]==0&&h[i].size()==2){int u=h[i][0],v=h[i][1];g[u].push_back(v);g[v].push_back(u);g[u+m].push_back(v+m);g[v+m].push_back(u+m);}else if(a[i]==1&&h[i].size()==2){int u=h[i][0],v=h[i][1];g[u].push_back(v+m);g[v].push_back(u+m);g[u+m].push_back(v);g[v+m].push_back(u);}}for(int i = 1; i <= m+m; i++){if(!dfn[i])tarjan(i);}for(int i = 1; i <= m; i++){if(belong[i]==belong[i+m]){puts("NO");return 0;}}puts("YES");
}
POJ3683：
题目大意:有n场婚礼，每场婚礼有个最早开始时间和最晚结束时间和持续时长，每场婚礼可以在开始时间举行，也可以在临近结束时举行使得婚礼结束时刚好是最晚结束时间，要求每场婚礼不能在时间上有交集，是否有一个合法的举办方案，若有，还需要打印方案。
每场婚礼只有2个选择，在前面举办或在后面举办，布尔运算即任意两个婚礼不能在时间轴上相交，同样是二元布尔运算(两个婚礼的时间段是否相交的判断)，很经典的2-sat模型，该题还需要打印一个可行方案。在有解的情况下（只要该点不与对立点在同一个连通分量），用tpsort给婚礼排序标定每场婚礼在前面举办或在后面举办，然后遍历打印即可。题目给的时间是hh:mm制，将时间转换为分钟即可。
这份代码常数略大，跑了400ms,抠了别人的代码才跑200ms
#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
int n;
string s,t;
const int maxn = 3e3+10;
struct wed{int sta;int en; int len;
}a[2500];
int change(string s){int res=0;res+=(s[0]-'0')*600;res+=(s[1]-'0')*60;res+=(s[3]-'0')*10;res+=(s[4]-'0');return res;
}
bool judge(int s1,int t1,int s2,int t2){ //判断是否相交 if(t1<=s2||t2<=s1) return 0;return 1;
}
vector<int> g[2*2500];
vector<int> h[maxn];
int dfn[maxn],belong[maxn],low[maxn],in[maxn],vis[maxn],cnt,res,top;
int ind[maxn],label[maxn],op[maxn];
void add(int x,int y){g[x].push_back(y);
}
void ad(int x,int y){h[x].push_back(y);ind[y]++;
}
void tarjan(int s){vis[s]=1;low[s]=dfn[s]=++cnt;in[++top]=s;for(int i = 0; i < g[s].size(); i++){if(!dfn[g[s][i]]) tarjan(g[s][i]);if(vis[g[s][i]]) low[s]=min(low[s],low[g[s][i]]);}if(low[s]==dfn[s]){++res;do{belong[in[top]]=res;vis[in[top]]=0;}while(in[top--]!=s);}
}
void build(){ //反向建图for(int i = 1; i <= n+n; i++)for(int j = 0; j < g[i].size(); j++){int v = g[i][j];if(belong[i]!=belong[v])ad(belong[v],belong[i]);}
}
void tpsort(){queue<int> pq;for(int i = 1; i <= res; i++)if(ind[i]==0) pq.push(i);while(!pq.empty()){int top=pq.front();pq.pop();if(!label[top]){label[top]=1;label[op[top]]=-1;}for(int i = 0; i < h[top].size(); i++){int v = h[top][i];ind[v]--;if(ind[v]==0) pq.push(v);}}
}
void print(int i,int key){if(key==1){int s=a[i].sta;int l=a[i].len+s;printf("%02d:%02d %02d:%02d\n",s/60,s%60,l/60,l%60);}else{int en=a[i].en;int t=en-a[i].len;printf("%02d:%02d %02d:%02d\n",t/60,t%60,en/60,en%60);}
}
int main(){scanf("%d",&n);int length;for(int i = 1; i <= n; i++){cin>>s>>t>>length;a[i].sta=change(s);a[i].en=change(t);a[i].len=length;}for(int i = 1; i <= n; i++){for(int j = i+1; j <= n; j++)int s1=a[i].sta,l1=a[i].len,t1=a[i].en;int s2=a[j].sta,l2=a[j].len,t2=a[j].en; if(judge(s1,s1+l1,s2,s2+l2)){ //4种可能相交情况及加边add(i,j+n);add(j,i+n);}if(judge(s1,s1+l1,t2-l2,t2)){add(i,j);add(j+n,i+n);}if(judge(t1-l1,t1,s2,s2+l2)){add(i+n,j+n);add(j,i);}if(judge(t1-l1,t1,t2-l2,t2)){add(i+n,j);add(j+n,i);}}}for(int i = 1; i <= n+n; i++){if(!dfn[i]) tarjan(i); //完成缩点 }for(int i = 1; i <= n; i++){op[belong[i]]=belong[i+n];op[belong[i+n]]=belong[i]; //标记新的对立结点 if(belong[i]==belong[i+n]){puts("NO");return 0;}}build(); //反向建图 tpsort();puts("YES");for(int i = 1; i <= n; i++){print(i,label[belong[i]]);}
}
更多推荐
寒假牛客基础训练2
发布评论