題目大意:機器調度問題,同一個任務可以在A,B兩台不同的機器上以不同的模式完成.機器的初始模式是mode_0,但從任何模式改變成另一個模式需要重啟機器.求完成所有工作所需最少重啟次數.
===================================================
對於任務(i,x,y),我們在A機mode_x與B機mode_y之間連一條邊.這樣,題目就變成了一個二分圖,我們的目的是完成所有任務,即覆蓋所有線段,題目要求選擇最少的點,使得每個線段至少有一個端點被選中(這個任務就被完成了),這就是最小點覆蓋模型,答案是這個二分圖的最大匹配.
但是這題我是用最大流水過的，可以增加一個超級源點和超級匯點分別和A，B機器的每個模式連一條邊權為一的邊，然後就是最大流了
注意起始時，機器都處在模式0！！
for(int i=0;i<k;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(b*c!=0)
map[b][c]=true;
}
下面是我的代碼
/********* PRO: POJ 1325 TIT: Machine Schedule DAT: 2013-08-16-15.50 AUT: UKean EMA: [email protected] *********/ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define INF 1e9 using namespace std; queue<int> que;//廣搜需要使用的隊列 int s,t;//源點和匯點 int flow[505][505];//殘流量 int p[505];//廣搜記錄路徑的父節點數組 int a[505];//路徑上的最小殘量 int cap[505][505];//容量網絡 int ans;//最大流 int read() { int n,m,k; cin>>n;if(!n) return 0; cin>>m>>k; s=0;t=m+n+1; //1->n 是A n+1 ->n+m是B memset(cap,0,sizeof(cap)); for(int i=0;i<k;i++) { int a,b,c;cin>>a>>b>>c; if(b*c!=0)//記住初始狀態為0 0 所以只要b或c中有一個為0，那麼就不用把它存入圖中了 cap[b+1][c+n+1]=1; } for(int i=1;i<=n;i++) cap[s][i]=1; for(int i=n+1;i<=n+m;i++) cap[i][t]=1; return 1; } int deal()//增廣路算法就不具體解釋了，詳細的解釋可以看我關於網絡流的第一篇博客 // http://blog.csdn.net/hikean/article/details/9918093 { memset(flow,0,sizeof(flow)); ans=0; while(1) { memset(a,0,sizeof(a)); a[s]=INF; que.push(s); while(!que.empty()) { int u=que.front();que.pop(); for(int v=0;v<=t;v++) if(!a[v]&&cap[u][v]-flow[u][v]>0) { p[v]=u; que.push(v); a[v]=min(a[u],cap[u][v]-flow[u][v]);//路徑上的最小殘流量 } } if(a[t]==0) break; for(int u=t;u!=s;u=p[u]) { flow[p[u]][u]+=a[t]; flow[u][p[u]]-=a[t]; } ans+=a[t]; } cout<<ans<<endl; return ans; } int main() { while(read()) deal(); return 0; }
