在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
/* 题意:给出递归函数: void go(int dep, int n, int m){ printf("%d\n",dep); if(dep<m&&x[a[dep]]+x[b[dep]]!=c[dep]) go(dep + 1, n, m); } 其中,a,b数组的元素小于n 数组长度为m,c数组的元素只有 0,1,2 数组长度为m, x数组的元素只有0,1现在给出a,b,c 数组的元素,问你这个输出的dep最大是多少,也就是递归最多的次数。 初步思路:分析条件:dep<m&&x[a[dep]]+x[b[dep]]!=c[dep] m是最大可能的递归次数,并且x[a[dep]]+x[b[dep]]!=c[dep] 实际上是x[a[dep]]+x[b[dep]]和c[dep]是不能共存的,也就是说有如下几种情况: c[dep]==0:x[a[dep]]和x[b[dep]],必定至少有一个为真 c[dep]==1:x[a[dep]]和x[b[dep]],只能都为真都为假 c[dep]==2:x[a[dep]]和x[b[dep]],不能都为真 由上面三种情况,二分递归的次数,判断的规则就是2-SAT跑的结果 */ #include<bits/stdc++.h> using namespace std; int t; int n,m; int a[10010],b[10010],c[10010],x[210]; /*********************************************2-SAT模板*********************************************/ const int maxn=10000+10; struct TwoSAT { int n;//原始图的节点数(未翻倍) vector<int> G[maxn*2];//G[i].j表示如果mark[i]=true,那么mark[j]也要=true bool mark[maxn*2];//标记 int S[maxn*2],c;//S和c用来记录一次dfs遍历的所有节点编号 //从x执行dfs遍历,途径的所有点都标记 //如果不能标记,那么返回false bool dfs(int x) { if(mark[x^1]) return false;//这两句的位置不能调换 if(mark[x]) return true; mark[x]=true; S[c++]=x; for(int i=0;i<G[x].size();i++) if(!dfs(G[x][i])) return false; return true; } void init(int n) { this->n=n; for(int i=0;i<2*n;i++) G[i].clear(); memset(mark,0,sizeof(mark)); } //加入(x,xval)或(y,yval)条件 //xval=0表示假,yval=1表示真 void add_clause(int x,int xval,int y,int yval)//这个地方不是一尘不变的,而是参照问题的约束条件进行加边 { G[2*x+xval].push_back(y*2+yval); } //判断当前2-SAT问题是否有解 bool solve() { for(int i=0;i<2*n;i+=2) if(!mark[i] && !mark[i+1]) { c=0; if(!dfs(i)) { while(c>0) mark[S[--c]]=false; if(!dfs(i+1)) return false; } } return true; } }TS; /*********************************************2-SAT模板*********************************************/ void build(int mid){ TS.init(n); for(int i=0;i<mid;i++){ switch(c[i]){ case 0: TS.add_clause(a[i],0,b[i],1); TS.add_clause(b[i],0,a[i],1); break;//不能都为假 case 1: TS.add_clause(a[i],0,b[i],0); TS.add_clause(b[i],0,a[i],0); TS.add_clause(a[i],1,b[i],1); TS.add_clause(b[i],1,a[i],1); break;//同真同假 case 2: TS.add_clause(a[i],1,b[i],0); TS.add_clause(b[i],1,a[i],0); break;//不能同真 } } } int main(){ // freopen("in.txt","r",stdin); scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d%d",&a[i],&b[i],&c[i]); } int l=0,r=m; while(l<=r){ int mid=(l+r)/2; build(mid); if(TS.solve()==true) l=mid+1; else r=mid-1; } printf("%d\n",l-1); } return 0; }
|
请发表评论