uestc 1651 Fill Numbers

タイトルリンク:uestc 1651 Fill Numbers
このテーマは确かにいいですね.その时、试合の时からガウスショ元のことばかり考えていましたが、最悪の场合は未知数が最大1000でしたが、私のガウスショ元モデルの时间再検査度はO(n^3)でほとんどできませんでした.ガウスショウ元なら,方程式ごとに最大2個の未知数しかないので,より優れたアルゴリズムが得られるに違いない.
スペースを点と見なし、1行に2つのスペースがある場合は、この2つのスペースの間に1つのエッジをつなぎ、列に2つのスペースがある場合は同じです.このようにして最後に形成された図は、以下のいくつかの連通ブロック1、1つの孤立した点に分けることができ、この点の値が行および列によって直接制約されることを示しているので、この点には一意の解があり、解がない可能性がある.2、1本のチェーンで、2つの端点はいずれも度が1の点であるため、2つの端点の値は行または列で一意に決定することができ、私たちは一端からdfsを始め、チェーン内の各点の値を順次求め、最後に別の端点の値が合法かどうかを判断すればよい.この場合も一意解があるか,あるいは無解である可能性がある.3、1つの環、よく考えてみると、1つの環に対して、1組の特解が存在すれば、必ず無限多組の実行可能な解を構築することができるので、私たちは1点を取って、1つの初期値を取ってdfsを開始して、環を鎖に分解して、環の中の1組の特解を求めて、もし特解が存在すれば、無限解があって、さもなくば解がありません.具体的には,度が1の点からdfsを開始し,対応する解をスペースに埋め込み,その後,すべての度が0の孤立点を処理し,最後にリングがあるか否かを判断し,リングがある場合は特解のセットを埋め込む.最後に、解が合法かどうかを統一的に判断する.
1、解法&&無環Unique 2、解法&&有環More than one 3、解法不合法No solution
証明第3点は実はよく証明されています.
ループが存在する場合、このループ内の定点個数は偶数個であり、1->2->3->4->1がループであり、(1,2)の和a、(2,3)と値b、(3,4)と値c、(4,1)と値dとすれば、
a+c=b+dは必ず無限多節が存在し,否定者は解けない

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int maxn=1010;
int n,m,a[maxn][maxn],row[maxn],col[maxn];
int x[maxn*2],y[maxn*2],degree[maxn*2];
vector g[maxn*2];
bool vis[maxn*2];

int cal(int u)
{
    int i;
    for(i=0;i=m){
       int tmp=0;
       for(int j=0;j