～技术宅真可怕～#1 - 2020-2-19 13:14
光速火箭
定義單向邊：若節點 i 和 k 之間相連，則其間有和兩條單向邊。現有 N 個節點和 E 條單向邊，其中N>=2且E/2>=1。
定義路徑的加法：若一條路徑的尾和另一條路徑的首相同，則
定義路徑的減法：
其中
定義環路：從某個節點出發經過若干個節點之後回到出發節點的路徑。
定義獨立環路集：該集合中的每一條環路都無法用該集合中的其他環路線性組合而成，但圖中的任意一條環路均可由該集合中的獨立環路線性組合（其中線性組合的係數為 1，0 或-1 ）而成。
易得一個獨立環路集中獨立環路的數量為 E-(N-1)。輸入節點及其連接狀況，求一個可行的獨立環路集。
輸入：
第一行為 偶數 E 和 自然數 N
接下來的 E/2 行為連接情況。均為雙向連接。
輸出：
E-(N-1)行，為一個可行的獨立環路集
兩個 example 的圖如下
我個人目前是知道先打印所有 i->j->i 的 E/2 條路徑的，但是剩下的 E/2-(N-1) 條路徑暫時還沒有頭緒。
i->k
k->i
定義路徑的加法：若一條路徑
i->...->j
j->...->k
i->path_p->j + j->path_q->k = i->path_p->j->path_q->k
定義路徑的減法：
i->path_p->j->path_q->k - i->path_p->j = j->path_q->k
其中
i->path_p->j != -(j->reverse_path_p->i)
定義環路：從某個節點出發經過若干個節點之後回到出發節點的路徑。
定義獨立環路集：該集合中的每一條環路都無法用該集合中的其他環路線性組合而成，但圖中的任意一條環路均可由該集合中的獨立環路線性組合（其中線性組合的係數為 1，0 或-1 ）而成。
易得一個獨立環路集中獨立環路的數量為 E-(N-1)。輸入節點及其連接狀況，求一個可行的獨立環路集。
輸入：
第一行為 偶數 E 和 自然數 N
接下來的 E/2 行為連接情況。均為雙向連接。
輸出：
E-(N-1)行，為一個可行的獨立環路集
Example input 1:
6 3
1 2
2 3
1 3
Example output 1:
1 2 1
2 3 2
3 1 3
1 2 3 1
Example input 2:
12 5
1 2
2 3
3 4
4 5
5 1
1 3
Example output 2:
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 3 1
1 2 3 1
1 3 4 5 1
兩個 example 的圖如下
我個人目前是知道先打印所有 i->j->i 的 E/2 條路徑的，但是剩下的 E/2-(N-1) 條路徑暫時還沒有頭緒。
另外你这个靠path定义cycle也不是特别标准的语言，一般cycle就简单地定义成边的子集，运算就取symmetric difference，然后这当然是一个order=2的Abelian group所以我们可以讨论basis。你那样还有一些无聊的麻烦要处理。。