设一个超级源点s，一个超级汇点t，各支队伍各为1个结点，各场比赛也各为1个结点，从s到各场比赛各连1条边，容量为3，从各场比赛到这场比赛的2支参赛队伍各连1条边，容量为3，最后从各支队伍向t各连1条边，容量为输入的对应得分。然后，跑一次最大流，若最大流为满流3 * n * (n-1) / 2，则得分是正确的，再根据各场比赛的流量输出相应的数据，否则得分是不正确的。
#include
#include
#include
#include
using namespace std;
const int maxv = 200 + 10;
const int maxn = 40000 + 10;
const int INF = 0x3f3f3f3f;
int a[maxv], vs[maxv][maxv];
struct Edge{
int u;
int v;
int cap;
int flow;
};
struct Dinic{
int n, m, s, t;
vector edges;
vector G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];
int addEdge(int uu, int vv, int cap){
edges.push_back((Edge){uu, vv, cap, 0});
edges.push_back((Edge){vv, uu, 0, 0});
m = edges.size();
G[uu].push_back(m-2);
G[vv].push_back(m-1);
return m-2;
}
bool bfs(){
memset(vis, 0, sizeof(vis));
queue qu;
qu.push(s);
d[s] = 0;
vis[s] = 1;
while(!qu.empty()){
int x = qu.front(); qu.pop();
int si = G[x].size();
for(int i = 0; i < si; i++){
Edge& e = edges[G[x][i]];
if(!vis[e.v] && e.cap > e.flow){
vis[e.v] = 1;
d[e.v] = d[x] + 1;
qu.push(e.v);
}
}
}
return vis[t];
}
int dfs(int x, int a){
if(x == t || a == 0) return a;
int flow = 0, f;
int si = G[x].size();
for(int& i = cur[x]; i < si; i++){
Edge& e = edges[G[x][i]];
if(d[x] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.cap-e.flow))) > 0){
e.flow += f;
edges[G[x][i]^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int s, int t){
this->s = s;
this->t = t;
int flow = 0;
while(bfs()){
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
};
int main()
{
int n;
while(scanf("%d", &n) == 1){
Dinic din;
int t = n + n * (n-1) / 2 + 1;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
din.addEdge(i, t, a[i]);
}
for(int i = 1, k = n+1; i <= n; i++)
for(int j = i+1; j <= n; j++, k++){
vs[i][j] = din.addEdge(0, k, 3);
din.addEdge(k, i, 3);
din.addEdge(k, j, 3);
}
if(din.Maxflow(0, t) == 3 * n * (n-1) / 2){
puts("CORRECT");
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++){
int L = din.edges[vs[i][j]+2].flow;
int R = din.edges[vs[i][j]+4].flow;
if(L == 3 && R == 0) printf("%d > %d\n", i, j);
else if(L == 0 && R == 3) printf("%d < %d\n", i, j);
else if(L == 2 && R == 1) printf("%d >= %d\n", i, j);
else printf("%d <= %d\n", i, j);
}
}
else puts("INCORRECT");
}