1. 完善程序(单选题,每题3分,共计30分)
1.给一个矩阵N* M,给你第i行1的个数和位置，让你选些行精确覆盖 M列(精确覆盖:每列有且只有1个1)。
例如:如下的矩阵:
11100001
10001110
10010110
00010010
00001100
就包含了这样一个集合(第1,4,5行)。
Input
多组数据,对于每组数据:
第一行两个整数N, M;
楼下来N行，每行开头一个整数x.表示该行上1的个数，接下来x个整数，每个1的位置。
Output
如果有解随意输出组集合，否则输出NO,中间空格隔开。
# include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 10000000000
# define N 2005
# define M 2000005
int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int n,m;
int h[N],s[N],q[N];
int u[M],d[M],L[M],R[M],C[M],X[M];
void del(int c) //delete ROW C
{
___(1)___;
___(2)___;
for(int i=d[c]; i!=c; i=d[i])
for(int j=R[i]; j!=i; j=R[j])
u[d[j]]= u[j],d[u[j]]=d[j],s[C[j]]--;
}
void add(int c)
{
L[R[c]]= R[L[c]]=c;
for(int i=u[c]; i!=c; i=u[i])
for(int j=L[i]; j!=i; j=L[j])
u[d[j]]= d[u[j]]=j,s[C[j]]++;
}
void link(int r,int c)
{
static int size=0;size++;
X[size]=r;C[size]=c;
s[c]++;
d[size]= d[c]; u[size]=c;
u[d[size]]=size;
d[u[size]]=size;
if(h[r]==-1)
h[r]=L[size]=R[size]=size;
else
{
R[size]=R[h[r]];
L[size]= h[r];
L[R[size]]=size;
R[L[size]]= size;
}
}
bool dance(int k)
{
if(R[0]=0)
{
printf("%d" ,k);
for(int i=1; i<=k; i++)
printf(" %d",X[q[i]]);
puts("");
return 1;
}
int mn=inf,c;
for(int i= R[0]; i; i=R[i])
if(s[i]<mn) mn=s[i],c=i;
___(3)___;
for(int i=d[c]; i!=c; i=d[i])
{
q[k+1]=i;
for(int j=R[i]; j!=i; j=R[j]) ___(4)___;
if(dance(k+1)) return 1;
for(int j=L[i]; j!=i; j=L[j]) ___(5)___;
}
add(c);
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0; i<=m; i++)
{
d[i]=u[i]=i;
L[i+1]=i;R[i]=i+1;
s[i]=0;
}
R[m]=0; size=m;
int x,y;
for(int i=1; i<=n; i++)
{
h[i]=-1;
x=read();
while(x--)
{
y=read();
link(i,y);
}
}
if(!dance(0)) puts("NO");
}
return 0;
}
选择题
1) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )
2. (树的直径)给定一颗n个节点的树，每条边有个长度wi，求这棵树直径的长度。树的直径是指树的最长简单路。
做法:两次BFS。开始任选一点u作为起点进行BFS，找到最远的一点s，再从s再次BFS找到最远的一点t。s-t两点的路径长度就是直径的长度。
# include <iostream>
# include <cstring>
using namespace std;
const int inf= 0x3f3f3f3f; //假设的无穷大值，具体数值为1061109567
const int maxn=1005;
struct Node{
int to,w,next; //临接表节点，to表示这条边的终点,w表示这条边的长度，next表示下一条边的编号
} edge[maxn*2];
int head[maxn],tot; //head[u]表示u的临接表头节点的标号
int n; //节点树
int dis[maxn]; //离起点的距离
bool vis[maxn]; //某个点是否已经拜访过
int que[maxn],first,last; //队列
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void addedge(int u,int v,int w)
{
edge[tot].to=v;
edge[tot].w= w;
edge[tot].next=head[u];
head[u]=tot++;
}
int BFS(int u)
{
first=last=0;
memset(dis,inf,sizeof(dis));
memset(vis,0, sizeof(vis));
dis[u]=0;
vis[u]=1;
que[last++]=u;
while(___(1)___)
{
u=que[first++];
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=dege[i].to;
if(___(2)___)
{
vis[v]=1;
que[last++];
___(3)___;
}
}
}
int tmp=1;
for(int i=2; i<=n; i++)
if(___(4)___) tmp=i;
return tmp;
}
int main()
{
int u,v,w,s,t;
cin>>n;
init();
for(int i=1; i<n; i++)
{
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
s=BFS(1);
___(5)___;
cout<< dis[t] << endl;
return 0;
}
选择题
1) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )