P2474 [SCOI2008]天平
题目背景
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。
输入输出样例
输入样例#1： 复制
6 2 5
?+????
-?+???
?-????
????+?
???-?+
????-?
输出样例#1： 复制
1 4 1
输入样例#2： 复制
14 8 4
?+???++?????++
-??=?=???????=
??????????=???
?=??+?==??????
???-???-???-??
-=????????????
-??=???=?-+???
???=+?=???????
??????????????
??????+???????
??=???-????-??
????+?????+???
-?????????????
-=????????????
输出样例#2： 复制
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*],E[maxn*];
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]=;
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]=;
gr[g][++gr[g][]]=x;
belong[x]=g;
}
belong[u]=g;
gr[g][++gr[g][]]=u;
vis[u]=;
top--;
}
}
queue<int>q;
int main(){
freopen("Cola.txt","r",stdin);
scanf("%d%d%d",&n,&A,&B);
for(int i=;i<=n;i++){
scanf("%s",s+);
for(int j=;j<=n;j++){
if(s[j]=='-')map[i][j]=-,map[j][i]=;
if(s[j]=='+')map[i][j]=,map[j][i]=-;
if(s[j]=='=')map[i][j]=,map[j][i]=;
}
}
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
if(map[i][j]==)Insert(j,i);//i>j连一条从j指向i的边
if(map[i][j]==-)Insert(i,j);//i<j连一条从i指向j的边
if(map[i][j]==)Insert(i,j),Insert(j,i);
}
}
for(int i=;i<=n;i++)if(!dfn[i])Tarjan(i);
for(int i=;i<=g;i++){
for(int j=;j<=gr[i][];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=;i<=g;i++){
if(du[i]==)q.push(i),wei[i]=;
}
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]==){
wei[to]=wei[now]+;
q.push(to);
}
}
}
for(int i=;i<=n;i++)w[i]=wei[belong[i]];
int c1=,c2=,c3=,sum=w[A]+w[B];
for(int i=;i<=n;i++){
if(i==A||i==B)continue;
for(int j=i+;j<=n;j++){
if(j==A||j==B)continue;
if(w[i]+w[j]<sum)c1+=;
if(w[i]+w[j]==sum)c2+=;
if(w[i]+w[j]>sum)c3+=;
}
}
cout<<c1<<' '<<c2<<' '<<c3;
}
20分 拓扑排序
/*
a+b>c+d可以转化为a-c>d-b，可以用差分约束求解
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 51
using namespace std;
int n,a,b,dx[maxn][maxn],dn[maxn][maxn];
char s[maxn];
int main(){
freopen("Cola.txt","r",stdin);
scanf("%d%d%d",&n,&a,&b);
for(int i=;i<=n;i++){
scanf("%s",s+);
for(int j=;j<=n;j++){
if(i==j||s[j]=='=')dx[i][j]=dn[i][j]=;
else if(s[j]=='+')dn[i][j]=,dx[i][j]=;
else if(s[j]=='-')dn[i][j]=-,dx[i][j]=-;
else dn[i][j]=-,dx[i][j]=;
}
}
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(k==i||k==j||i==j)continue;
dn[i][j]=max(dn[i][j],dn[i][k]+dn[k][j]);
dx[i][j]=min(dx[i][j],dx[i][k]+dx[k][j]);
}
int c1=,c2=,c3=;
for(int i=;i<=n;i++){
if(i==a||i==b)continue;
for(int j=;j<i;j++){
if(j==a||j==b)continue;
if(dn[a][i]>dx[j][b]||dn[b][i]>dx[j][a])c1++;
if(dn[i][a]>dx[b][j]||dn[i][b]>dx[a][j])c3++;
if((dn[a][i]==dx[a][i]&&dn[j][b]==dx[j][b]&&dn[a][i]==dn[j][b]) || (dn[a][j]==dx[a][j]&&dn[i][b]==dx[i][b]&&dn[a][j]==dn[i][b]))c2++;
}
}
printf("%d %d %d",c1,c2,c3);
}
100分 差分约束
