2008四川NOI省选
你有n个砝码,均为1克,2克或者3克。你并不清楚每个砝码的重量,但你知道其中一些砝码重量的大小关系。你把其中两个砝码A 和B 放在天平的左边,需要另外选出两个砝码放在天平的右边。问:有多少种选法使得天平的左边重(c1)、一样重(c2)、右边重(c3)?(只有结果保证惟一的选法才统计在内)
输入格式:
第一行包含三个正整数n,A,B(1<=A,B<=N,A 和B 不相等)。砝码编号
为1~N。以下n行包含重量关系矩阵,其中第i行第j个字符为加号“+”表示砝
码i比砝码j重,减号“-”表示砝码i比砝码j 轻,等号“=”表示砝码i和砝码
j一样重,问号“?”表示二者的关系未知。存在一种情况符合该矩阵。
输出格式:
仅一行,包含三个整数,即c1,c2和c3。
- 6 2 5
- ?+????
- -?+???
- ?-????
- ????+?
- ???-?+
- ????-?
- 1 4 1
- 14 8 4
- ?+???++?????++
- -??=?=???????=
- ??????????=???
- ?=??+?==??????
- ???-???-???-??
- -=????????????
- -??=???=?-+???
- ???=+?=???????
- ??????????????
- ??????+???????
- ??=???-????-??
- ????+?????+???
- -?????????????
- -=????????????
- 18 12 11
4<=n<=50
- /*
- w[i]<w[j]就连一条i->j的边
- w[i]=w[j]就连一条双向边
- 跑Tarjan把图缩成有向无环图
- 最后入度为0的点的质量就是1,按拓排给其他的赋值为2,3
- 由于少考虑了一些情况,导致不合法的情况也会统计到答案中,所以炸了
- */
- #include<iostream>
- #include<cstdio>
- #include<queue>
- #define maxn 51
- using namespace std;
- int n,A,B,belong[maxn],wei[maxn],w[maxn],cnt,map[maxn][maxn],du[maxn];
- int num,head[maxn],dfn[maxn],low[maxn],st[maxn],top,g,gr[maxn][maxn];
- int Num,Head[maxn];
- double vis[maxn];
- struct node{
- int to,pre;
- }e[maxn*2],E[maxn*2];
- char s[maxn];
- void Insert(int from,int to){
- e[++num].to=to;
- e[num].pre=head[from];
- head[from]=num;
- }
- void Insert2(int from,int to){
- E[++Num].to=to;
- E[Num].pre=Head[from];
- Head[from]=Num;
- }
- void Tarjan(int u){
- cnt++;
- dfn[u]=low[u]=cnt;st[++top]=u;vis[u]=1;
- for(int i=head[u];i;i=e[i].pre){
- int v=e[i].to;
- if(!dfn[v]){
- Tarjan(v);
- low[u]=min(low[u],low[v]);
- }
- else if(vis[v])low[u]=min(low[u],dfn[v]);
- }
- if(dfn[u]==low[u]){
- g++;
- while(st[top]!=u){
- int x=st[top];
- top--;vis[x]=0;
- gr[g][++gr[g][0]]=x;
- belong[x]=g;
- }
- belong[u]=g;
- gr[g][++gr[g][0]]=u;
- vis[u]=0;
- top--;
- }
- }
- queue<int>q;
- int main(){
- freopen("Cola.txt","r",stdin);
- scanf("%d%d%d",&n,&A,&B);
- for(int i=1;i<=n;i++){
- scanf("%s",s+1);
- for(int j=1;j<=n;j++){
- if(s[j]==‘-‘)map[i][j]=-1,map[j][i]=1;
- if(s[j]==‘+‘)map[i][j]=1,map[j][i]=-1;
- if(s[j]==‘=‘)map[i][j]=2,map[j][i]=2;
- }
- }
- for(int i=1;i<=n;i++){
- for(int j=i+1;j<=n;j++){
- if(map[i][j]==1)Insert(j,i);//i>j连一条从j指向i的边
- if(map[i][j]==-1)Insert(i,j);//i<j连一条从i指向j的边
- if(map[i][j]==2)Insert(i,j),Insert(j,i);
- }
- }
- for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
- for(int i=1;i<=g;i++){
- for(int j=1;j<=gr[i][0];j++){
- int now=gr[i][j];
- for(int k=head[now];k;k=e[k].pre){
- int to=e[k].to;
- if(belong[now]!=belong[to])
- Insert2(belong[now],belong[to]),du[belong[to]]++;
- }
- }
- }
- for(int i=1;i<=g;i++){
- if(du[i]==0)q.push(i),wei[i]=1;
- }
- while(!q.empty()){
- int now=q.front();q.pop();
- for(int i=Head[now];i;i=E[i].pre){
- int to=E[i].to;
- du[to]--;
- if(du[to]==0){
- wei[to]=wei[now]+1;
- q.push(to);
- }
- }
- }
- for(int i=1;i<=n;i++)w[i]=wei[belong[i]];
- int c1=0,c2=0,c3=0,sum=w[A]+w[B];
- for(int i=1;i<=n;i++){
- if(i==A||i==B)continue;
- for(int j=i+1;j<=n;j++){
- if(j==A||j==B)continue;
- if(w[i]+w[j]<sum)c1+=1;
- if(w[i]+w[j]==sum)c2+=1;
- if(w[i]+w[j]>sum)c3+=1;
- }
- }
- cout<<c1<<‘ ‘<<c2<<‘ ‘<<c3;
- }
来源: http://www.bubuko.com/infodetail-2381517.html