给你一个m*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。
最大点权独立集,应用最小割求解
构图:
增加源点s和汇点t.每个格子作为一个点,进行黑白染色(相邻的一黑一白).
源点到所有黑点引一条权为黑点点权的边.所有白点到汇点引一条权为白点点权的边.
每个黑点到与其相邻的白点引一条权为无穷的边.
结果:所有点权之和减去最小割容量(即最大流流量).
分析:
因为最大流不是无穷的,所以最小割中不会包含(黑点到白点的)无穷边.所以任意不包含无穷边的割都是一种选择方案.为什么必须是割呢?因为若割中的每一条边对应这一个不选取的点,则去掉这些点之后,原图中便不存在s--u--v--t的路的,即选择的点中没有相邻的u和v了.自然当割为最小割时,剩下的点的权和最大,为所求结果.
大概就是这样子了吧,不知道有没有理解错......
描述:有A,B俩机器,各有0~n-1和0~m-1种模式.有k个任务,既可在A的某种模式下运行又可在B的某种模式下进行,求最小的模式转换次数(A,B初始为模式0).
牛人:
每个任务化为一条线，它连接着a[i]和b[j]，问题转化为求（a[]和b[]中）最少的点， 使得每条线都至少有一个端点被选（这个任务就完成了）。这个就是最小点覆盖的模型了
所以是:
scanf("%d%d%d",&j,&x,&y);
if(x*y!=0)
map[x][y]=1;
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n,m;
bool map[105][105];
int match[105];
bool v[105];
bool dfs(int p)
{
int i;
for (i = 1; i <= m; i++)
{
if (map[p][i] && !v[i])
{
v[i] = 1;
if (match[i] == -1 || dfs(match[i]))
{
match[i] = p;
return 1;
}
}
}
return 0;
}
int Hungry()
{
int i;
int ans = 0;
memset(match,-1,sizeof(match));
for (i = 1; i <= n; i++)
{
memset(v, false, sizeof(v));
if (dfs(i))
ans++;
}
return ans;
}
int main()
{
freopen("in", "r", stdin);
freopen("out", "w", stdout);
int i,k,j,x,y;
while(scanf("%d%d%d",&n,&m,&k)!=EOF && n!=0)
{
memset(map,false,sizeof(map));
for (i = 1; i <= k; i++)
{
scanf("%d%d%d",&j,&x,&y);
if(x*y!=0)
map[x][y]=1;
}
printf("%d\n",Hungry());
}
}
转自:http://aceeca1.frostbytez.com/index.php/archives/SPFA%E4%BC%98%E5%8C%96
SLF：Small Label First 策略。
实现方法是，设队首元素为 ，队列中要加入节点
，在
时加到队首而不是队尾，否则和普通的 SPFA 一样加到队尾。
LLL：Large Label Last 策略。
实现方法是，设队列 中的队首元素为
，距离标号的平均值为
，每次出队时，若
，把
移到队列末尾，如此反复，直到找到一个
使
，将其出队。
初始化为-1,计算传递闭包过程中赢记为1，输记为0，最后检查传递闭包中无-1的行数或列数。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int adj[101][101];
int tc[101][101];
int main()
{
//freopen("in.txt","r",stdin);
int n,m,v,w,i,s,t,ans;
scanf("%d%d",&n,&m);
memset(adj,-1,sizeof(adj));
for(i=1; i<=n; i++) adj[i][i]=1;
for(i=1; i<=m; i++)
{
scanf("%d%d",&v,&w);
adj[v][w]=1;
}
for(s=1; s<=n; s++)
for(t=1; t<=n; t++)
tc[s][t]=adj[s][t];
for(i=1;i<=n;i++)
for(s=1;s<=n;s++)
if(tc[s][i]>0)
for(t=1;t<=n;t++)
if(tc[i][t]>0) {tc[s][t]=1;tc[t][s]=0;}
// for(s=1; s<=n; s++)
// {
// for(t=1; t<=n; t++)
// printf("%3d ",tc[s][t]);
// cout<<endl;
// }
ans=n;
for(s=1; s<=n; s++)
for(t=1; t<=n; t++)
if(tc[s][t]==-1)
{
ans--;
break;
}
printf("%d\n",ans);
return 0;
}
firefox崩溃了，害我打的字儿没了……
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int cow[10001];
int scow[10001];
int pos[100001];
bool hasg[10001];
int main()
{
freopen("in","r",stdin);
int n,allmin,gsum,glen,gmin,tans,ans;
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",cow+i);
scow[i]=cow[i];
}
sort(scow,scow+n);
allmin=scow[0];
for(i=0;i<n;i++)
pos[scow[i]]=i;
memset(hasg,0,sizeof(bool)*n);
ans=0;
for(int i=0;i<n;i++)
{
if(!hasg[i])//new group
{
hasg[i]=1;
gsum=cow[i];glen=1;gmin=cow[i];
j=i;
while(!hasg[pos[cow[j]]])
{
j=pos[cow[j]];
hasg[j]=1;
gsum+=cow[j];
++glen;
if(gmin>cow[j]) gmin=cow[j];
}
tans=min(gsum+(glen-2)*gmin,
gsum+gmin+(glen+1)*allmin);
ans+=tans;
}
}
printf("%d",ans);
}
