二分图。
最大点权独立集=总权-最小点权覆盖集。
哪位大神能给一些二分图 最大点权独立集等等 的相关资料!!!!!跪谢
用网络流求解最小点权覆盖集即可,建图不讲了。
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<queue> #include<algorithm> using namespace std; #define min(a,b) a>b?b:a const int maxn=2550,maxm=500000,inf=1000000000; struct Edge { int v,f,nxt; }; int g[maxn+50]; int nume; struct Edge e[maxm+50]; int number[70][70]; int m,n; int src,sink; bool vis[maxn+10]; int dist[maxn+10]; void add(int u,int v,int f) { e[++nume].v=v; e[nume].f=f; e[nume].nxt=g[u]; g[u]=nume; e[++nume].v=u; e[nume].f=0; e[nume].nxt=g[v]; g[v]=nume; } bool is_n(int y) { if(y>=1&&y<=n) return true; return false; } bool is_m(int x) { if(x>=1&&x<=m) return true; return false; } void Init() { int i,j; for(i=1;i<=m;i++) for(j=1;j<=n;j++){ if((i+j)%2==0){ add(0,(i-1)*n+j,number[i][j]); int tempy1=j-1; int tempy2=j+1; if(is_n(tempy1)) add((i-1)*n+j,(i-1)*n+tempy1,inf); if(is_n(tempy2)) add((i-1)*n+j,(i-1)*n+tempy2,inf); int tempx1=i-1; int tempx2=i+1; if(is_m(tempx1)) add((i-1)*n+j,(tempx1-1)*n+j,inf); if(is_m(tempx2)) add((i-1)*n+j,(tempx2-1)*n+j,inf); } else add((i-1)*n+j,sink,number[i][j]); } } void bfs() { int i; queue<int >que; memset(dist,0,sizeof(dist)); while(!que.empty()) que.pop(); que.push(src); vis[src]=true; while(!que.empty()){ int u=que.front(); que.pop(); for(i=g[u];i;i=e[i].nxt){ if(e[i].f && !vis[e[i].v]){ dist[e[i].v]=dist[u]+1; que.push(e[i].v); vis[e[i].v]=true; } } } } int dfs(int u,int delta) { int i; if(u==sink) return delta; else{ int ret=0; for(i=g[u];i&δi=e[i].nxt){ if(e[i].f&&dist[e[i].v]==dist[u]+1){ int dd=dfs(e[i].v,min(delta,e[i].f)); e[i].f-=dd; e[i^1].f+=dd; delta-=dd; ret+=dd; } } return ret; } } int dinic() { int ret=0; while(true){ memset(vis,0,sizeof(vis)); bfs(); if(!vis[sink]) return ret; ret+=dfs(src,inf); } } int main() { int i,j; while(scanf("%d%d",&m,&n)!=EOF){ nume=1; src=0;sink=n*m+1; memset(g,0,sizeof(g)); int sum=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++){ scanf("%d",&number[i][j]); sum+=number[i][j]; } Init(); printf("%d\n",sum-dinic()); } return 0; }