Content Distribution Networks have been attracted a great deal of attraction in recent years. Replica placement problems (RPPs) as one of the key technologies in the Content Distribution Networks have been widely studied. In this paper, we propose an optimization model with server storage capacity constraints for the RPPs. Furthermore, part of the objective function is represented as a Multiple Minimum Cost Flow Model for the first time. Efficient algorithms are designed to minimize the total network cost. The algorithms include three parts: replication algorithm preprocess, constraint P-median model and algorithm of solving constraint P-median models. Correctness of the algorithms is proved by two theorems. In the simulation, we compare our algorithms to other heuristic methods numerically. The results show that our algorithms perform better with less cost. Future work should be concentrated on the more meticulous models with other resources constraints of the RPPs.