1樓：yummy
作為乙個OIer，想幫你解決問題，但是你的問題對我而言不夠清晰/kk
如果只要構造一種方案，只要第k個同學批第k+1 mod m,k+2 mod m,...,k+n mod m張卷子，線性完成。
如果求方案數，網路流貌似做不到，回朔法的速度也很感人。
我們重新審視乙個問題，目標是在m*m的矩陣裡面填入m*n個數，使得每行每列都有n個數。
而根據回朔法，前n排是可以隨便填一定不會被剪枝的，因此我們可以確定時間複雜度不小於 ，可以在一天內解決mn<40的情況。
唉，剛才想到一種解法，可惜有漏數的情況。
我覺得存在一種O(2^n*2^m)的解法，初步想法是轉化為矩陣填數問題，然後狀壓已知部分和未知部分的輪廓線。
2樓：兜兜裡沒得糖
轉化為有向圖問題，m個人/份試卷，用m個頂點代替，出度代表給別人批試卷的個數，入度代表被批閱個數，那麼就是求滿足任一頂點，出度=入度=n的乙個邊組合，剩下的就靠你自己了，上課了
3樓：
上面回溯法寫得很清楚了，不過當n稍微增大一些的時候會很慢。這裡說一下網路流的思路。
下面說一下建圖方法。
有n個人和m份試卷，假設人的編號為i，他的試卷編號為i + n。
首先建立乙個超級原點S和超級匯點T（這兩個點隨便編號，只要不和1 ~ n + m重合就行）。
每個人不能批改他自己的試卷，可以批其他人的試卷最多一次，所以我們就從每個i向n + 1~n + m（除了i + n）的m - 1個點連一條容量為1的邊。
每個人只能批改n份試卷，所以我們從源點S向所有人1 ~ n各連線一條容量為n的邊；每份試卷只能被批改n次，所以從每份試卷n + 1~ n + m各向匯點連線一條容量為n的邊，然後跑最大流即可。最後根據跑完最大流邊的連線情況就能推出誰批改了哪些卷子。
時間複雜度比較玄學，不過寫的好的Dinic演算法n = 1000左右的資料應該是能跑的。
上課摸魚手機碼的字，所以不方便配圖，勉強看文字吧。
4樓：
從給所有其他人批卷（n』=m-1）這種情況下生成乙個布林矩陣，然後減小n』直到n迭代清零即可，圖示是一種填零方式。
這題本質就是生成乙個橫豎看都是n的矩陣，這種解法複雜度O是quadratic，優化之後（每行集中處理m-1 - n的情況）會更快。
最終的不同答案是行或者列的排列不同，因為更換排列不會改變矩陣橫豎是n這種特性
如何用C語言程式設計這個題？
tearing include intmain 霍工 include int main int salary,i,n 0,bill 5 clrscr printf Input salary scanf d salary for i 0 i 5 i n salary bill i salary sal...
C語言（其他程式語言）的規定都是有原因的嗎？
熊爸爸科技工坊 無語了，那說明你壓根還不懂什麼是科學，所謂的科學並不是世界的真理，也只不過是一種解釋世界的宗教罷了。科學來自於宗教，本來得目的就是為了證明上帝的存在，但是後來發現對科學了解的越多人類原來可以自己成為上帝，科學沒有否定上帝等宗教，只是告訴我們掌握了科學我們也能如上帝一般無所不能。而且科...
如何快速學好c語言的程式設計？
The One 建議從實踐出發，比如現在就去用C語言寫乙個桌面程式，你就會去了解寫乙個桌面程式具體需要用到哪些東西，哪些函式庫，不需要按著教材上的順序學，把你的想法變成實際，如果沒有想法就去模仿一些簡單的專案做個demo來完善自己的skills，你真正應該掌握的不是C語言，而是學習能力和解決問題的能...