Special Fish
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1018 Accepted Submission(s): 384
Problem Description
There is a kind of special fish in the East Lake where is closed to campus of Wuhan University. It’s hard to say which gender of those fish are, because every fish believes itself as a male, and it may attack one of some other fish who is believed to be female by it.
A fish will spawn after it has been attacked. Each fish can attack one other fish and can only be attacked once. No matter a fish is attacked or not, it can still try to attack another fish which is believed to be female by it.
There is a value we assigned to each fish and the spawns that two fish spawned also have a value which can be calculated by XOR operator through the value of its parents.
We want to know the maximum possibility of the sum of the spawns.
A fish will spawn after it has been attacked. Each fish can attack one other fish and can only be attacked once. No matter a fish is attacked or not, it can still try to attack another fish which is believed to be female by it.
There is a value we assigned to each fish and the spawns that two fish spawned also have a value which can be calculated by XOR operator through the value of its parents.
We want to know the maximum possibility of the sum of the spawns.
Input
The input consists of multiply test cases. The first line of each test case contains an integer n (0 < n <= 100), which is the number of the fish. The next line consists of n integers, indicating the value (0 < value <= 100) of each fish. The next n lines, each line contains n integers, represent a 01 matrix. The i-th fish believes the j-th fish is female if and only if the value in row i and column j if 1.
The last test case is followed by a zero, which means the end of the input.
The last test case is followed by a zero, which means the end of the input.
Output
Output the value for each test in a single line.
Sample Input
3
1 2 3
011
101
110
0
Sample Output
6
Author
momodi@whu
Source
Recommend
notonlysuccess
1,KM:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=110; const int INF=0x3f3f3f3f; int n; int linker[N],lx[N],ly[N],slack[N]; int visx[N],visy[N],w[N][N]; int val[N]; int DFS(int x){ visx[x]=1; for(int y=1;y<=n;y++){ if(visy[y]) continue; int tmp=lx[x]+ly[y]-w[x][y]; if(tmp==0){ visy[y]=1; if(linker[y]==-1 || DFS(linker[y])){ linker[y]=x; return 1; } }else if(slack[y]>tmp){ //不在相等子图中slack 取最小的 slack[y]=tmp; } } return 0; } int KM(){ int i,j; memset(linker,-1,sizeof(linker)); memset(ly,0,sizeof(ly)); for(i=1;i<=n;i++) //lx初始化为与它关联边中最大的 for(j=1,lx[i]=-INF;j<=n;j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; for(int x=1;x<=n;x++){ for(i=1;i<=n;i++) slack[i]=INF; while(1){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(DFS(x)) //若成功(找到了增广轨),则该点增广完成,进入下一个点的增广 break; //若失败(没有找到增广轨),则需要改变一些点的标号,使得图中可行边的数量增加。 //方法为:将所有在增广轨中(就是在增广过程中遍历到)的X方点的标号全部减去一个常数d, //所有在增广轨中的Y方点的标号全部加上一个常数d int d=INF; for(i=1;i<=n;i++) if(!visy[i] && d>slack[i]) d=slack[i]; for(i=1;i<=n;i++) if(visx[i]) lx[i]-=d; for(i=1;i<=n;i++) //修改顶标后,要把所有不在交错树中的Y顶点的slack值都减去d if(visy[i]) ly[i]+=d; else slack[i]-=d; } } int res=0; for(i=1;i<=n;i++){ if(linker[i]==-1 || w[linker[i]][i]==-INF) return -1; res+=w[linker[i]][i]; } return res; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n) && n){ memset(w,0,sizeof(w)); for(int i=1;i<=n;i++) scanf("%d",&val[i]); char ch; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ cin>>ch; if(ch=='1') w[i][j]=val[i]^val[j]; } printf("%d\n",KM()); } return 0; }
2,最小费用最大流
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int VM=1010; const int EM=10100; const int INF=0x3f3f3f3f; struct Edge{ int u,v,nxt; int flow,cost; }edge[EM<<1]; int n,cnt,head[VM],val[VM]; int pre[VM],dis[VM],vis[VM]; void addedge(int cu,int cv,int cw,int cc){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].flow=cw; edge[cnt].cost=cc; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].u=cv; edge[cnt].v=cu; edge[cnt].flow=0; edge[cnt].cost=-cc; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } int src,des; int SPFA(){ queue<int> q; while(!q.empty()) q.pop(); for(int i=0;i<=des;i++){ dis[i]=INF; vis[i]=0; pre[i]=-1; } dis[src]=0; vis[src]=1; q.push(src); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].v; if(edge[i].flow>0 && dis[v]>dis[u]+edge[i].cost){ dis[v]=dis[u]+edge[i].cost; pre[v]=i; if(!vis[v]){ vis[v]=1; q.push(v); } } } } return pre[des]!=-1; } int mincost(){ int ans=0; while(SPFA()){ int u=des,minf=INF; while(u!=src){ minf=min(minf,edge[pre[u]].flow); u=edge[pre[u]].u; } u=des; while(u!=src){ edge[pre[u]].flow-=minf; edge[pre[u]^1].flow+=minf; u=edge[pre[u]].u; } ans+=dis[des]; } return -ans; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n) && n){ cnt=0; memset(head,-1,sizeof(head)); for(int i=0;i<n;i++) scanf("%d",&val[i]); int w; for(int i=0;i<n;i++){ addedge(0,i+1,1,0); addedge(i+1,n+n+1,1,0); addedge(n+i+1,n+n+1,1,0); for(int j=0;j<n;j++){ scanf("%1d",&w); if(w) addedge(i+1,n+j+1,1,-(val[i]^val[j])); } } src=0; des=n+n+1; printf("%d\n",mincost()); } return 0; }
相关推荐
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码