Markov Random Fields (MRF's) can be used for a wide variety of vision problems. In this paper we address the estimation of first-order MRF's with a particular clique potential that resembles a well. We show that the maximum {\em a posteriori} estimate of such an MRF can be obtained by solving a multiway cut problem on a graph. This allows the application of near linear-time algorithms for computing provably good approximations. We formulate the visual correspondence problem as an MRF in our framework, and show that this yields quite promising results on real data with ground truth.