题目链接：https://cn.vjudge.net/contest/209473#problem/B
题目大意：对于n个数字，给出sum[j]-sum[i](sum表示前缀和)的符号（正负零），求一组n个数的的可行解（n个数都在-10——10之间）【保证一定有解】
解题思路：
第一反应！差分约束！
差分约束是用来求解不等式组的合理解的，用在此题上刚好，把sum[i]-sum[j]>0转化为sum[i]-sum[j]>=-1，小于零同理。把sum[i]-sum[j]==0转化为sum[i]-sum[j]>=0,sum[j]-sum[i]>=0.
差分约束之后会在另一个专题里讲到，会此方法的同学已经可以建图跑最短路了，不会此方法的同学建议选择第二种方法拓扑排序。【但是推荐差分约束，因为感觉比拓排简单】
后来和别的同学交流讨论，才知道这道题正解，或者说官方解是拓扑排序。
把大小关系改成单向连边，比如本鶸的丑代码就是把大的前缀和引出一条边指向小的前缀和。
特殊点在于等于零的处理，想了半个小时（好弱啊），想到一个很丑陋的方法，就是把两个相等的点的大小关系完全复制。也就是说如果sum[A]==sum[B]，那么所有连接A却没有连接B的边，全加在B上，所有连接B没有连接A的边，全加在A上，无论方向。
第二个特殊点在于控制n个数的大小，如果选择差分约束只需要把上限值改成10就行了，对于拓排，我就想了个丑方法，把最大的前缀和赋为10*n，往下每一层减1，由于题目保证一定有解，所以不会出现问题。
下面放代码：
差分约束6msAC代码：
/* by Lstg */
/* 2018-01-27 15:32:28 */ #include<stdio.h>
#define inf 102000000 int map[][]; int main(){ int T,i,j,n,k;
char t;
scanf("%d",&T);
while(T--){ scanf("%d",&n);
getchar();
for(i=;i<=n+;i++)
for(j=;j<=n+;j++)
if(i!=j)map[i][j]=inf;
for(i=;i<=n;i++)
for(j=i;j<=n;j++){
t=getchar();
if(t=='+')map[j][i-]=-;
else if(t=='-')map[i-][j]=-;
else
map[i-][j]=map[j][i-]=; }
for(i=;i<=n;i++)
map[n+][i]=;
n++;
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
for(i=;i<n;i++)
printf("%d ",map[n][i]-map[n][i-]);
putchar();
}
return ;
}
拓扑排序6msAC代码：
/* by Lstg */
/* 2018-03-04 00:11:12 */ #include<stdio.h>
#include<string.h> int sum[],g[][],du[],stk[],n; void _getans(){ int i,top=,p;
for(i=;i<=n;i++)
if(!du[i]){
stk[++top]=i;
sum[i]=*n;
}
while(top){
p=stk[top--];
for(i=;i<=n;i++)
if(g[p][i]){
du[i]--;
if(!du[i]){
sum[i]=sum[p]-;
stk[++top]=i;
}
}
}
} int main(){ int T,i,j,k;
char ch[]; scanf("%d",&T);
while(T--){ memset(du,,sizeof(du));
memset(g,,sizeof(g));
memset(sum,,sizeof(sum));
scanf("%d",&n); scanf("%s",ch);
k=;
for(i=;i<n;i++)
for(j=i+;j<=n;j++){
if(ch[k]=='+'){
g[j][i]=true;
du[i]++;
}
if(ch[k]=='-'){
g[i][j]=true;
du[j]++;
}
k++;
}
k=;
for(i=;i<n;i++)
for(j=i+;j<=n;j++)
if(ch[k++]=='')
for(int a=;a<=n;a++){
if(!g[i][a]&&g[j][a]){
g[i][a]=true;
du[a]++;
}
if(!g[j][a]&&g[i][a]){
g[j][a]=true;
du[a]++;
}
if(!g[a][i]&&g[a][j]){
g[a][i]=true;
du[i]++;
}
if(!g[a][j]&&g[a][i]){
g[a][j]=true;
du[j]++;
}
}
_getans(); for(i=;i<=n;i++) printf("%d ",sum[i]-sum[i-]);
putchar();
}
return ;
}