http://poj.org/problem?id=1776
?
題意:
poj1741?有一個機器要完成N個作業,
給你一個N*N的矩陣,
M[i][j]=1,表示完成第i個作業后不用重啟機器,繼續去完成第j個作業
M[i][j]=0,表示如果做完第i個作業,想要繼續去做第j個作業,那么必須重啟機器
poj2352。對于任意兩個作業都有M[i][j] = 1或者M[j][i] = 1.
求出完成這N個作業啟動機器的最少次數,以及每次啟動完成作業的數量和這些作業的順序
初始時機器處于關閉狀態.
?
poj1208,將M當做圖,就是找最少的路徑條數覆蓋所有的點
最小路徑覆蓋?
但不能保證圖是二分圖,所以不能用匈牙利算法
題目中說對于任意兩個作業都有M[i][j] = 1或者M[j][i] = 1
所以這張圖是在競賽圖的基礎上加了幾條邊
而競賽圖一定存在一條哈密頓通路
所以一定只需要一次開機完成所有作業
然后就是輸出競賽圖上的一條哈密頓通路
詳請參見文章http://www.cnblogs.com/TheRoadToTheGold/p/8439160.html
?
#include<cstdio> #include<cstring> #include<iostream>using namespace std;#define N 1001int n; char s[N<<1]; int e[N][N];int front,nxt[N];int st[N];void Hamilton() {front=1;memset(nxt,0,sizeof(nxt));for(int i=2;i<=n;++i){if(e[front][i]){nxt[i]=front;front=i;continue;}int j,k;for(j=front;j;k=j,j=nxt[j])if(e[j][i]){nxt[i]=j;nxt[k]=i;break;}if(!j) nxt[k]=i;} }void print() {printf("1\n%d\n",n);int now=front;int top=0;while(now){st[++top]=now;now=nxt[now];}for(int i=top;i>1;--i) printf("%d ",st[i]);printf("%d\n",st[1]); }int main() {while(scanf("%d",&n)!=EOF){memset(e,false,sizeof(e));for(int i=1;i<=n;++i) {getchar();scanf("%[^\n]",s);int t=0;for(int j=0;t<n;j+=2) e[i][++t]=s[j]-'0';}Hamilton();print();} }
?
Time Limit:?1000MS | ? | Memory Limit:?65536K | ||
Total Submissions:?2637 | ? | Accepted:?763 | ? | Special Judge |
Description
ACM works in a really special way. The machine can finish one task in a short time, after it's finishing one task, it should smoothly move to the next one, otherwise the machine will stop automatically. You must start it up again to make it continue working. Of course, the machine cannot move arbitrarily from one task to another. So each time before it starts up, one task sequence should be well scheduled. Specially, a single task also can be regarded as a sequence. In the sequence, the machine should be able to smoothly move from one task to its successor (if exists). After started up, the machine always works according to the task sequence, and stops automatically when it finishes the last one. If not all the tasks have been finished, the machine has to start up again and works according to a new sequence. Of course, the finished tasks can't be scheduled again.?
For some unknown reasons, it was guaranteed that for any two tasks i and j, the machine can smoothly move from i to j or from j to i or both. Because the startup process is quite slow, Tom would like to schedule the task sequences properly, so that all the tasks can be completed with minimal number of startup times. It is your task to help him achieve this goal.
Input
Input is terminated by end of file.
Output
Sample Input
3 0 1 1 1 0 1 0 0 0
Sample Output
1 3 2 1 3
Source