Hint

Consider the principle of "turning difficulty around." Transform the complex mutual constraints of triangles into a simple in-degree assignment problem.

Construct a network flow model where different flows correspond to different costs. When moving from $$$\operatorname{flow}_i$$$ to $$$\operatorname{flow}_{i+1}$$$, the change in $$$\Delta \operatorname{cost}$$$ follows a certain pattern. Then, split the total flow of $$$n$$$ into $$$n$$$ unit-capacity edges with differential costs. Finally, leverage the nature of cost flow to let it find the optimal solution by itself.

Main Text

Let $$$d_i$$$ be the in-degree.

Consider minimizing the number of non-triangles. Observe that if $$$(A,B,C)$$$ does not form a triangle, we have: $$$d_A = 2, d_B = 1, d_C = 0$$$. Thus, the number of non-triangles is $$$\sum\limits_i \binom{d_i}{2} = \sum\limits_i \frac{d_i(d_i - 1)}{2}$$$.

So the goal is to minimize $$$\sum\limits_i \binom{d_i}{2} = \sum\limits_i \frac{d_i(d_i - 1)}{2}$$$.

Construct a cost flow network to restrict the direction of each edge using flow. Specifically, for each undirected edge $$$E(i,j)$$$ and vertices $$$P(i), P(j)$$$, create edges $$$E(i,j) \to P(i)$$$ and $$$E(i,j) \to P(j)$$$. Also, add a source $$$S \to E(i,j)$$$ with capacity $$$1$$$.

For each $$$P(i)$$$, when it receives $$$x$$$ units of flow, it incurs a cost of $$$\frac{x(x-1)}{2}$$$. But how to handle the fact that each unit of flow can correspond to different costs?

We can do this: for each $$$P(i)$$$, connect $$$n$$$ edges from $$$P(i)$$$ to the sink $$$T$$$, each with capacity $$$1$$$ and costs $$$0, 1, 2, \dots$$$ respectively. Then, run minimum cost maximum flow.