題目鏈接
題目大意：有n件工作要分配給n個(gè)人做。第i個(gè)人做第j件工作產(chǎn)生的效益為c[i][j]。求最優(yōu)/最壞收益
題解：二分圖最大權(quán)匹配問(wèn)題，可以用費(fèi)用流或KM算法(表示不會(huì)) 把所有人看做二分圖中頂點(diǎn)Xi，所有工作看做二分圖中頂點(diǎn)Yi，建立附加源S匯T。
1、從S向每個(gè)Xi連一條容量為1，費(fèi)用為0的有向邊。 2、從每個(gè)Yi向T連一條容量為1，費(fèi)用為0的有向邊。 3、從每個(gè)Xi向每個(gè)Yj連接一條容量為1，費(fèi)用為Cij的有向邊。
求最小費(fèi)用最大流，最小費(fèi)用流值就是最少運(yùn)費(fèi)，求最大費(fèi)用最大流，最大費(fèi)用流值就是最多運(yùn)費(fèi)。
PS:我在做bzoj1070的時(shí)候用了這種思想建模，結(jié)果WA了，后來(lái)發(fā)現(xiàn)居然還有原題233
我的收獲：我一般用0作源點(diǎn)，注意要初始化0。匯點(diǎn)可以選一個(gè)比較大的點(diǎn)(我一般習(xí)慣用點(diǎn)數(shù)+1) 最短路邊權(quán)取反就是最長(zhǎng)路(不需要修改初始化)
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int M=550;#define INF 0x3f3f3f3fint n,m,t,st,ed,ans,tot;bool vis[M];int head[M],d[M],PRe[M],mp[M][M];queue<int> q;struct edge{int fro,to,nex,c,val;}e[M*M];void add(int i,int j,int ca,int co){e[t].fro=i,e[t].to=j,e[t].nex=head[i],e[t].c=ca,e[t].val=co;head[i]=t++;}void insert(int i,int j,int w,int z){add(i,j,w,z),add(j,i,0,-z);}bool spfa(){ for(int i=0;i<=ed;i++) vis[i]=0,d[i]=INF; d[st]=0;q.push(st); while(!q.empty()) { int u=q.front();q.pop();vis[u]=false; for(int i=head[u];i!=-1;i=e[i].nex){ int v=e[i].to; if(e[i].c&&d[v]>d[u]+e[i].val){ d[v]=d[u]+e[i].val; pre[v]=i; if(!vis[v]){ vis[v]=true; q.push(v); } } } } return d[ed]!=INF;}void flow(){ int mx=INF; for(int u=ed;u!=st;u=e[pre[u]].fro) mx=min(mx,e[pre[u]].c); for(int u=ed;u!=st;u=e[pre[u]].fro){ e[pre[u]].c-=mx;e[pre[u]^1].c+=mx; ans+=mx*e[pre[u]].val; }}void build(int k){ t=0;memset(head,-1,sizeof(head));ans=0; for(int i=1;i<=n;i++) insert(st,i,1,0); for(int i=1;i<=n;i++) insert(i+n,ed,1,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) insert(i,j+n,1,k*mp[i][j]);}void work(){ build(1);while(spfa()) flow(); printf("%d/n",ans); build(-1);while(spfa()) flow(); printf("%d/n",-ans);//邊權(quán)變成相反數(shù)就能求最長(zhǎng)路了}void init(){ int x,y,z,w;t=0; cin>>n;st=0;ed=n*2+1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]);}int main(){ init(); work(); return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
