HDU2255 模板 难度x
HDU2282 思维 难度XXx
HDU3722 模板 难度X
HDU3395 模版
HDU1533 最小值模型 难度x
HDU2853
HDU3523
HDU1533
HDU3488
HDU2448 +最短路
HDU2255
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
using namespace std;
const int maxn=;
const int inf=0x7ffffff;
int map[maxn][maxn];
int vis1[maxn],vis2[maxn];
int ex1[maxn],ex2[maxn];
int lack[maxn];
int link[maxn];
int ans,n;
bool _bfs(int v)
{
vis1[v]=true;
for(int i=;i<=n;i++){
if(!vis2[i]){
int tmp=ex1[v]+ex2[i]-map[v][i];
if(tmp==){
vis2[i]=true;
if(!link[i]||_bfs(link[i])){
link[i]=v;
return true;
}
}
else if(tmp<lack[i]) lack[i]=tmp;
}
}
return false;
}
void _KM()
{
int t,i,j;
memset(link,,sizeof(link));
memset(ex2,,sizeof(ex2));
for(i=;i<=n;i++){
ex1[i]=map[i][];
for(j=;j<=n;j++)
if(ex1[i]<map[i][j]) ex1[i]=map[i][j];
}
for(t=;t<=n;t++){
for(i=;i<=n;i++) lack[i]=inf;//思考：为什么在这里？
while(true){
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
if(_bfs(t)) break;
int gap=inf;
for(i=;i<=n;i++)
if(!vis2[i]&&lack[i]<gap) gap=lack[i];
for(i=;i<=n;i++) if(vis1[i]) ex1[i]-=gap;
for(i=;i<=n;i++) if(vis2[i]) ex2[i]+=gap;
for(i=;i<=n;i++) if(!vis2[i])lack[i]-=gap;
}
}
ans=;
for(i=;i<=n;i++) ans+=map[link[i]][i];
printf("%d\n",ans);
}
int main()
{
int i,j;
while(~scanf("%d",&n)){
for(i=;i<=n;i++)
for(j=;j<=n;j++) scanf("%d",&map[i][j]);
_KM();
}
return ;
}
HDU1533
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=;
const int inf=0x7ffffff;
int map[maxn][maxn];
int vis1[maxn],vis2[maxn];
int ex1[maxn],ex2[maxn];
int lack[maxn];
int link[maxn];
int ans,n;
int x1[maxn],x2[maxn],y[maxn],y2[maxn];
int Abs(int v){
if(v<) v=-v;
return v;
}
bool _bfs(int v)
{
vis1[v]=true;
for(int i=;i<=n;i++){
if(!vis2[i]){
int tmp=ex1[v]+ex2[i]-map[v][i];
if(tmp==){
vis2[i]=true;
if(!link[i]||_bfs(link[i])){
link[i]=v;
return true;
}
}
else if(tmp<lack[i]) lack[i]=tmp;
}
}
return false;
}
void _KM()
{
int t,i,j;
memset(link,,sizeof(link));
memset(ex2,,sizeof(ex2));
for(i=;i<=n;i++){
ex1[i]=map[i][];
for(j=;j<=n;j++)
if(ex1[i]<map[i][j]) ex1[i]=map[i][j];
}
for(t=;t<=n;t++){
for(i=;i<=n;i++) lack[i]=inf;//思考：为什么在这里？
while(true){
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
if(_bfs(t)) break;
int gap=inf;
for(i=;i<=n;i++)
if(!vis2[i]&&lack[i]<gap) gap=lack[i];
for(i=;i<=n;i++) if(vis1[i]) ex1[i]-=gap;
for(i=;i<=n;i++) if(vis2[i]) ex2[i]+=gap;
for(i=;i<=n;i++) if(!vis2[i])lack[i]-=gap;
}
}
ans=;
for(i=;i<=n;i++)
ans-=map[link[i]][i];
ans=ans;
printf("%d\n",ans);
}
int main()
{
int i,j,m,cnt1,cnt2;
char c;
while(~scanf("%d%d",&n,&m)){
if(n==&&m==) return ;
cnt1=cnt2=;
for(i=;i<=n;i++)
for(j=;j<=m;j++) {
cin>>c;
if(c=='H') {
x1[++cnt1]=i;y[cnt1]=j;
}
if(c=='m'){
x2[++cnt2]=i;y2[cnt2]=j;
}
}
n=cnt1;
for(i=;i<=n;i++)
for(j=;j<=n;j++){
map[i][j]=-(Abs(x1[i]-x2[j])+Abs(y[i]-y2[j]));
}
_KM();
}
return ;
}
HDU2282
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=;
const int inf=0x7ffffff;
int map[maxn][maxn];
int vis1[maxn],vis2[maxn];
int ex1[maxn],ex2[maxn];
int lack[maxn];
int link[maxn];
int ans,n;
int x[maxn],p[maxn],y[maxn],cnt1,cnt2;
int Abs(int v){
if(v<) v=-v;
return v;
}
bool _bfs(int v)
{
vis1[v]=true;
for(int i=;i<=cnt2;i++){
if(!vis2[i]){
int tmp=ex1[v]+ex2[i]-map[v][i];
if(tmp==){
vis2[i]=true;
if(!link[i]||_bfs(link[i])){
link[i]=v;
return true;
}
}
else if(tmp<lack[i]) lack[i]=tmp;
}
}
return false;
}
void _KM()
{
int t,i,j;
memset(link,,sizeof(link));
memset(ex2,,sizeof(ex2));
for(i=;i<=cnt1;i++){
ex1[i]=map[i][];
for(j=;j<=cnt2;j++)
if(ex1[i]<map[i][j]) ex1[i]=map[i][j];
}
for(t=;t<=cnt1;t++){
for(i=;i<=cnt2;i++) lack[i]=inf;//思考：为什么在这里？
while(true){
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
if(_bfs(t)) break;
int gap=inf;
for(i=;i<=cnt2;i++)
if(!vis2[i]&&lack[i]<gap) gap=lack[i];
for(i=;i<=cnt1;i++) if(vis1[i]) ex1[i]-=gap;
for(i=;i<=cnt2;i++) if(vis2[i]) ex2[i]+=gap;
for(i=;i<=cnt2;i++) if(!vis2[i])lack[i]-=gap;
}
}
ans=;
for(i=;i<=cnt2;i++)
ans-=map[link[i]][i];
printf("%d\n",ans);
}
int main()
{
int i,j,m;
char c;
while(~scanf("%d",&n)){
memset(map,,sizeof(map));
cnt1=cnt2=;
for(i=;i<=n;i++) scanf("%d",&p[i]);
for(i=;i<=n;i++){
while(p[i]>) {
x[++cnt1]=i;
p[i]--;
}
if(p[i]==) y[++cnt2]=i;
}
for(i=;i<=cnt1;i++)
for(j=;j<=cnt2;j++)
map[i][j]=-min(Abs(x[i]-y[j]),n-Abs(x[i]-y[j]));
_KM();
}
return ;
}
HDU3722
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<string.h>
using namespace std;
const int maxn=;
const int inf=0x7ffffff;
char c[][];
int map[maxn][maxn];
int vis1[maxn],vis2[maxn];
int ex1[maxn],ex2[maxn];
int lack[maxn];
int link[maxn];
int ans,n;
int x1[maxn],x2[maxn],y[maxn],y2[maxn];
int _get(int u,int v){
int i,j=,L1=strlen(c[u]+),L2=strlen(c[v]+);
for(i=L1;i>=;i--){
j++;
if(j>L2||c[u][i]!=c[v][j]){
j--;break;
}
}
return j;
}
bool _bfs(int v)
{
vis1[v]=true;
for(int i=;i<=n;i++){
if(!vis2[i]){
int tmp=ex1[v]+ex2[i]-map[v][i];
if(tmp==){
vis2[i]=true;
if(!link[i]||_bfs(link[i])){
link[i]=v;
return true;
}
}
else if(tmp<lack[i]) lack[i]=tmp;
}
}
return false;
}
void _KM()
{
int t,i,j;
memset(link,,sizeof(link));
memset(ex2,,sizeof(ex2));
for(i=;i<=n;i++){
ex1[i]=map[i][];
for(j=;j<=n;j++)
if(ex1[i]<map[i][j]) ex1[i]=map[i][j];
}
for(t=;t<=n;t++){
for(i=;i<=n;i++) lack[i]=inf;
while(true){
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
if(_bfs(t)) break;
int gap=inf;
for(i=;i<=n;i++)
if(!vis2[i]&&lack[i]<gap) gap=lack[i];
for(i=;i<=n;i++) if(vis1[i]) ex1[i]-=gap;
for(i=;i<=n;i++) if(vis2[i]) ex2[i]+=gap;
for(i=;i<=n;i++) if(!vis2[i])lack[i]-=gap;
}
}
ans=;
for(i=;i<=n;i++)
ans+=map[link[i]][i];
ans=ans;
printf("%d\n",ans);
}
int main()
{
int i,j;
while(~scanf("%d",&n)){
for(i=;i<=n;i++) scanf("%s",c[i]+);
for(i=;i<=n;i++)
for(j=;j<=n;j++){
if(i==j) map[i][j]=;
else map[i][j]=_get(i,j)；
}
_KM();
}
return ;
}