UValive4255 Guess

本文主要是介绍UValive4255 Guess，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
//放一个vjudge的罢

差分约束系统。

需要开一点点脑洞，转化为前缀和之间的大小关系然后建图跑拓扑排序。

CODE：（又长又丑又慢的代码）

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 15
struct edge
{int nxt,to,dis;
}a[10000];
char s[N][N];
int head[N],dis[N],in[N];
int T,n,num;
queue<int> q;
inline int max(const int &a,const int &b){return a>b?a:b;}
inline void add(int x,int y,int z)
{a[++num].nxt=head[x],a[num].to=y,a[num].dis=z,head[x]=num;
}
inline void topologysort()
{for(int i=0;i<=n;i++)if(!in[i]) q.push(i),dis[i]=0;while(!q.empty()){int tmp=q.front();q.pop();for(int i=head[tmp];i;i=a[i].nxt){dis[a[i].to]=max(dis[a[i].to],dis[tmp]+a[i].dis);in[a[i].to]--;if(!in[a[i].to]) q.push(a[i].to);}}
}
int main()
{scanf("%d",&T);while(T--){num=0;memset(head,0,sizeof(head));scanf("%d",&n);for(int i=0;i<=n;i++)dis[i]=0;for(int i=n;i;i--)for(int j=n-i+1;j<=n;j++){char c=getchar();while(c!='+'&&c!='-'&&c!='0') c=getchar();s[n-i+1][j]=c;}for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(s[i][j]=='+') add(i-1,j,1),in[j]++;else if(s[i][j]=='-') add(j,i-1,1),in[i-1]++;else add(i-1,j,0),in[j]++;topologysort();for(int i=1;i<=n;i++)printf("%d ",dis[i]-dis[i-1]);puts("");}return 0;
}

这篇关于UValive4255 Guess的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---